离散化
①：要求保序
排序、判重、二分
vector<int>alls; int find(int x){ //二分 int l = 0, r = alls.size(); while(l < r){ int mid = l+ r >> 1; if(alls[mid] >= x)r = mid; else l = mid + 1; } return r + 1; } sort(alls.begin(),alls.end()); //排序 alls.erase(unique(alls.begin(),alls.end()),alls.end()); //判重
②：不要求保序
map或hash表
int n; map<int,int>s; int get(int x) { if (s.count(x) == 0)s[x] = ++n; return s[x]; }
AcWing 802. 区间和
假定有一个无限长的数轴，数轴上每个坐标上的数都是0。
现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。
接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行，每行包含两个整数x和c。
再接下里 m 行，每行包含两个整数l和r。
输出格式
共m行，每行输出一个询问中所求的区间内数字和。
数据范围
代码
#include<iostream> #include<vector> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int, int>PII; const int N = 300010; int a[N], s[N]; vector<int>alls; vector<PII>add, query; int find(int x){ int l = 0, r = alls.size(); while(l < r){ int mid = l+ r >> 1; if(alls[mid] >= x)r = mid; else l = mid + 1; } return r + 1; } int main(){ int n,m;cin >> n >>m; for(int i=1;i<=n;++i){ int x,c;cin >> x >>c; alls.push_back(x); add.push_back({x,c}); } for(int i=1;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 it:add){ int x = find(it.first); a[x] += it.second; } for(int i = 1;i<=alls.size();++i){ s[i] = s[i - 1] + a[i]; } for(auto it :query){ int l = find(it.first); int r = find(it.second); printf("%d\n",s[r] - s[l - 1]); } return 0; }
