题目描述

做n次插入，m次查询
n m
插入
x c
求区间和
l r

样例

例子：2 2//插入两次，求两次区间和
1 2
1 3//对位置1的数加了一次2，一次3
-1 3
1 2
本题的思路是做一个占地面积小的查询表：原坐标x，现坐标find（x），值a[find(x)]
然后只对现坐标定义数组，数组就不会过于稀疏了
哪些原坐标需要一个现坐标？由于是求区间和，所以为零的数相当于不存在，只需要存非零的位置和值。即：
1、做了插入操作的x（如果对于同一个位置做了两次插入，第二次不应分配空间，但是读入为了方便，不作
区分，全部放入all，后面统一去重）
2、l和r：我们要求区间和，首先要确定区间的起始位置，给出的lr是原坐标，如果不给lr对应的现坐标，
find（x）是不存在的，从而无法确定原坐标的区间对应的现坐标的区间，区间和更是无从谈起。
代码：all.push_back(x);all.push_back(l);all.push_back(r);

接下来，为了确定区间，还需要排序（（x，l，r）插入的时候是乱序的）和去重

去重其实解决了两个问题：
1、两次插入都是对同一个位置，即如上push_back(1)做了两次
2、l和r是已经插入过的位置
获得了all：-1，1，2，3
1，2，3，4是它们的现坐标（因为要求前缀和所以从坐标一开始）

接下来考虑find（x）
要在all中找一个元素（原坐标）并返回其坐标（现坐标）：使用二分法

接下来考虑值：利用之前读入的add(x,c)将值放入数组a

获取a的前缀和数组s

利用find获得现坐标下的lr，利用前缀和数组求区间和的公式s[r]-s[l-1]（O（n）-〉O（1））。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int,int>PII;//因为要存数对
int const N=100010;
int n,m,a[N],s[N];//只有m，n这种后面可能要用到n--的输入变量才需要定义全局变量
vector<int>alls;
vector<PII> add,query;//插入和查询操作的数对；
int find(int x){//返回的是a数组中的下标
    int l=0,r=alls.size()-1;
    while(l<r){
    int mid=l+r>>1;
    if(alls[mid]>=x)r=mid;
    else l=mid+1;}
    return r+1;//保证现坐标都是从1算起
}
vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for (int i = 0; i < a.size(); i ++ )
        if (!i || a[i] != a[i - 1])//i=0的时候没有i-1，所以特殊算
            a[j ++ ] = a[i];//因为是先排的序，所以重复的数一定挨着
            //只有不重复的数才会被存下来，存完了之后，j再自加，所以是存到了j-1
    // a[0] ~ a[j - 1] 所有a中不重复的数
    //vec.erase(vec.begin()+i,vec.begin()+j);删除区间[i,j-1];区间从0开始
    return a.begin() + j;//最后一个不重复的数的下一个位置
}
int main(){
    //输入所有数据备用
    cin>>n>>m;
    for(int i=0;i<n;i++){int x,c;scanf("%d %d\n",&x,&c);
    //像x，c，l，r这样的后面还要用的有特定含义的，且后面需要的是干净的新变量的输入变量，就在循环里面定义，免得影响到别人
    add.push_back({x,c});alls.push_back(x);}
    for(int i=0;i<m;i++){int l,r;scanf("%d %d\n",&l,&r);
    query.push_back({l,r});alls.push_back(l);alls.push_back(r);}

    //处理alls,排序去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls), alls.end());

    //插入,形成稠密数组a
    for(auto item:add){
        int x=find(item.first);//根据find函数的最后一步可以知道，x是从1算起的，（不像alls是从0开始）
        a[x]+=item.second;
    }

    //为了求区间和预处理a的前缀和数组s（a的下标从1到n）
    for(int i=1;i<=alls.size();i++)s[i]=s[i-1]+a[i];//注意这里i的范围不是插入操作的数量。

    //处理查询
    for(auto item:query){
        int l=find(item.first),r=find(item.second);//注意这里一定是现数组的下标，要查一下的
        cout<<s[r]-s[l-1]<<endl;
    }
}