题目
假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。
输出格式
共m行,每行输出一个询问中所求的区间内数字和。
数据范围
−10^9≤x≤10^9,
1≤n,m≤10^5,
−10^9≤l≤r≤10^9,
−10000≤ c ≤10000
区间和 – 离散化
这题为什么要做离散化?
首先题目强调了这是一个无限长的数组,数轴的范围为 -1e+9 ~ 1e+9 , 如果这里简单的定义,即用其相应的下标表示其位置,那数组的长度至少是 2 * 1e+9; 这种数组长度就很长,但却编译不过的,因为超出栈空间,爆栈
报错信息如下:
故这种方法不可取,但因为考虑到虽然这个数轴的长度很长,但其对应的n操作和m操作最多如果不重复也就最多有 3 * 1e+5 个数据信息, 这个长度是可以定义数组的。即这时要考虑离散化,将原本数轴上一个很大的位置映射到较小的数组的其中一个位置之中。故这就是为哈这道题目要离散化的原因
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using PII = pair<int,int>; // 存储内容为pair的vector用于存储m个操作中要处理的求和区间
constexpr int N = 3*(1e+5) + 10; // 这里的数据不能只是 1e+5 , 测试数据会爆掉,段错误,因为 1≤n,m≤10^5, 首先在n次操作中在一个位置加上一个数,如果这n个位置不重复那最多要 1e+5 长度,然后m次操作中,区间的位置 l ,r 如果这m个区间都左右端点都不相同则最多要2 * 1e+5 个长度 。 故综合这数组的长度最少要 3 * 1e+5;
int n,m;
int arr[N]; // 离散后的数组
vector<PII> A, C; // A用于保存n个操作中的每次要操作的位置,和每次这个位置上加上的值 C用于保存m个操作中,每次操作的左右区间
vector<int> B; // B 用于保存需要离散化的位置,其离散化数据对应的vector下标可以被映射到arr数组中
int m_find(int x) // 根据传入的x值找到哦其在B中存放的位置, 例如我想在数轴3000位置映射到那里,3000这个值可能加入到B中的第0个位置,那么其就被映射到的位置就是 0 + 某个常数(取决于映射规则,这里的话会映射到arr数组的 1 这个位置)
{
int l = 0, r = B.size() - 1, mid; // 二分查找,根据要操作的数轴上的值,根据m_find函数的映射关系,在B中找到一个值为等于其数轴位置的值,其下标 + 1返回作为在arr数组上映射的值,为啥是 + 1 , 是因为要前缀和操作需要,这样比较方便。
while(r > l)
{
mid = l + r >> 1;
if(B[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; ++i)
{
int x,c;
cin >> x >> c;
A.emplace_back(x,c);
B.push_back(x);
}
for(int i = 0; i < m; ++i)
{
int l, r;
cin >> l >> r;
C.emplace_back(l,r); // 注意这里离散的话,同样要被进行求和的区间加入到B中,防止求前缀和的时候出现找不到映射的位置。
B.push_back(l);
B.push_back(r);
}
sort(B.begin(), B.end()); // 先排序是为了使用 unique 进行去重, 所谓的去重是把相邻相同的都放到了后面去,然后unique的返回值是一个迭代器,它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。
B.erase(unique(B.begin(),B.end()), B.end()); // 所以这里配合 erase 和 unique 达到真正去重
for(auto item : A) // 执行 n 次操作中的将 对应位置 加上 c, 这里遍历A , 因为A的每一个元素的first保存的就是数组上的对应位置,将其作为m_find函数返回其映射后在arr上的位置
{
int x = m_find(item.first);
arr[x] += item.second;
}
for(int i = 1; i <= B.size(); ++i) arr[i] += arr[i-1]; // 求前缀和
for(auto item : C) // 处理m个操作中的求区间和
{
int l = m_find(item.first), r = m_find(item.second); // 首先找到其左右端点映射的位置
cout << arr[r] - arr[l - 1] << endl;
}
return 0;
}
```