1.离散化
离散化：适合条件 （数字的值域非常大，但是个数非常少）
什么是离散化：把值域大的数字的序列映射到从0开始的自然数数组里（无法开辟出值域那么大的数组）
注意：① a中可能有重复元素，需要去重（erase,unique）
② 算出a[i]离散化后的值，需要使用二分思想
③离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量
2.题目描述
输入样例：
3 3 1 2 3 6 7 5 1 3 4 6 7 8
输出样例：
8 0 5
3.代码实现
思路：
利用离散化的思想，映射数字
#include <bits/stdc++.h> using namespace std; const int N = 300010; int a[N],s[N]; //原数组和前缀和数组 vector<int> alls; //存储离散化后下标的数组 typedef pair<int,int> PII; //定义pair类型 vector<PII> add,query; //插入和查找的数据结构 //二分索引 int findx(int x) { int l=0,r=alls.size()-1; while(l<r) { int mid=(l+r)/2; if(alls[mid]>=x) r=mid; else l=mid+1; } return r+1; } int main() { int n,m; cin>>n>>m; for(int i=0;i<n;i++) //预处理插入 { int x,c; cin>>x>>c; add.push_back({x,c}); alls.push_back(x); } for(int i=0;i<m;i++) //预处理查询 { int l,r; cin>>l>>r; query.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()); //处理插入 for(auto item : add) { int x=item.first,c=item.second; a[findx(x)] += c; } //求前缀和 for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i]; //处理查询 for(auto item : query) { int l=findx(item.first),r=findx(item.second); printf("%d\n",s[r]-s[l-1]); } return 0; }
