假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
AC代码：
#include#include #include using namespace std; const int N = 3 * 100010; vector alls; typedef pair PII; vector add, query; int a[N], s[N]; int find(int x){ //二分查找 int l = 0, r = alls.size() - 1; while(r > l){ int mid = (l + r) / 2; if(alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; } int main(){ int n, m, x, c, l, r; PII temp; cin >> n >> m; for(int i = 0; i < n; i++){ //处理输入 cin >> x >> c; //x代表位置，c代表数值 temp.first = x; temp.second = c; add.push_back(temp); alls.push_back(x); } for(int i = 0; i < m; i++){ //处理输入 cin >> l >> r; alls.push_back(l); alls.push_back(r); temp.first = l; temp.second = r; query.push_back(temp); } sort(alls.begin(), alls.end()); //排序 alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重 for(auto t : add) a[find(t.first)] += t.second; //处理插入，find函数完成映射 for(int i = 1; i <= alls.size(); i++) s[i] += s[i - 1] + a[i]; //计算前缀和数组的值 for(auto t : query) cout << s[find(t.second)] - s[find(t.first) - 1] << endl; //输出结果 return 0; }
理解：这个题目真的快到天花板了，我这个菜鸡看了好长时间才勉强理解。乍一看，想着用之前做过的前缀和的知识来做，但是数轴范围是10的-9次方到10的9次方，不能申请这么大的数组（内存超限）而且还有负数，需要经过一定的处理。
其基本思路就是将无限长的数轴的一部分下标映射到有限的数组内，具体映射哪些元素下标呢？就是将需要加上c的位置下标，和每次查询范围l，r这两个下标，将所有的这些下标映射到数组内，再设置一个find函数，这个函数是映射的关键，就是通过原始位置来查找到映射之后的下标，本质上就是一个二分查找算法，找到这个下标之后，就将这个下标所对应的元素加上c，这样就完成了初始化操作。接下来的操作就简单了，利用前缀和的知识，计算出这个序列的前缀和数组，用s[N]保存起来，再利用find函数将l，r映射到a[N]对应的下标,然后再求这对下标对应的区间前缀和就行了。
思路还是挺难想的，而且用到了STL的知识，都不是很熟悉，希望继续努力，希望能有突破！
说的不对的地方还请多多指教，谢谢
