目录

用于解决的问题类型：

作用：

使用到的函数：

常用模板：

例题引入：

题目：

解题思路：

代码详解：

---

用于解决的问题类型：

对于值域比较大，但个数比较少的问题（例如值域为1~1e9，个数为1e5）

作用：

将原来在数组中对应的下标，按照从小到大（升序）映射到alls中

使用到的函数：

vector<int> alls;
unique(alls.begin(),alls.begin())
//将元素去重，把重复的元素放到后面，并返回第一个重复元素的迭代器（即重复元素的begin()）

vc.erase(unique(alls.begin(),alls.begin()),vc.end());
//去掉后面的重复元素

int find(int x){//返回下标映射在alls中的值
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;//这里加1的原因是离散化的下标一般从1开始
}
//注lower_bound(alls.begin(),alls.end(),x)为从头到为二分查找大于等于x的第一个数的下标

常用模板：

vector<int> alls;//存储所有还没有进行离散化的数据
sort(alls.begin(),alls.end());//从小到大排
int find(int x){//找到x对应在alls中的下标
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
}

例题引入：

题目：

解题思路：

对坐标进行离散化，然后进行操作，得到结果

代码详解：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;

const int N=3e5+6;//最多能放入在alls中的下标的个数
int a[N],s[N];
int n,m;

vector<int> alls;
vector<PII> query,add;

int find(int x){
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
}

int main(){
    cin>>n>>m;
    
    int x,c;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&c);
        add.push_back({x,c});
        alls.push_back(x);//x下标需要使用，所以放入
    }
    
    int l,r;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        alls.push_back(l);//l下标需要使用，所以放入
        alls.push_back(r);//r下标需要使用，所以放入
        query.push_back({l,r});
    }
    
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    for(auto i:add){
        int x=find(i.first);
        a[x]+=i.second;
    }
    
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];//构造前缀和数组
    
    for(auto i:query){
        int l=find(i.first);
        int r=find(i.second);
        
        printf("%d\n",s[r]-s[l-1]);
    }
    return 0;
}