题目描述：
假定有一个无限长的数轴，数轴上每个坐标上的数都是 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
大体思路
首先看到了求区间内的和，那就可以利用前缀和来求，在看看其他描述，无限长的数轴，但是给出了n和m的范围，所以这个数组是有最多存放的大小的，只能放这么多数，但是x的范围是远大于我们求出来的数组上限大小的，就可以利用离散化来讲数组内的元素映射到一个容器当中，那这个题的大概思路就是用离散化加前缀和来求，对于数据来说，因为有成对出现的数据，所以我们可以使用pair来存放，可以定义两个pair类型的容器，一个用于存放x和c，一个用于存放l和r，废话不多说，上代码(带注释)：
usingnamespacestd; constintN=300010;//题目上能用到最大多的数就是2n+m，n和m都是10^5intn, m; inta[N], s[N];//a是原数组，s是前缀和vector<int>alls;//alls用于对a数组内的元素进行映射，离散化操作vector<pair<int, int>>add, qu;//add用于在哪个点加多少，qu存放的是区间，l和r，所以两个都用pair存放intfind(intx) { //利用二分查找到x在哪intl=0, r=alls.size() -1; while(l<r) { intmid=l+r>>1; if (alls[mid] >=x)r=mid; elsel=mid+1; } returnr+1;//这里返回r+1是因为后面要使用前缀和，r+1可以让前缀和不考虑边界问题} intmain() { cin>>n>>m; for (inti=0; i<n; i++) { intx, c; cin>>x>>c; add.push_back({ x,c });//add存放在哪个点加多少，点是x，c是加多少alls.push_back(x);//讲要加的点映射到vector容器当中 } for (inti=0; i<m; i++) { intl, r; cin>>l>>r; qu.push_back({ l,r });//存放要求的区间的两个端点alls.push_back(l);//将要计算的左端点映射到数组当中alls.push_back(r);//将要计算的右端点映射到数组当中 } //去重sort(alls.begin(), alls.end());//使内部离散化之后是有序的alls.erase(unique(alls.begin(), alls.end()), alls.end());//利用unique函数进行去重//unique会将内部元素的重复元素全都放到后面，然后返回后面全是重复元素区间开始的第一位迭代器，再利用erase删除掉这些重复元素//查找到x的位置，并且加上我们要加的数for (autoitme : add) { intx=find(itme.first);//查找到x的位置a[x] +=itme.second;//加上要加的值 } //计算出前缀和for (inti=1; i<=alls.size(); i++)s[i] =s[i-1] +a[i]; //利用qu内部存放的端点，用前缀和相减得到答案for (autoitme : qu) { intl=find(itme.first), r=find(itme.second); cout<<s[r] -s[l-1] <<endl; } return0; }
