离散化
什么事离散化?
离散化的本质是将已知序列建立新的下标索引,最终来缩小目标区间,并且可以结合二分,前缀和等算法进行额外的操作
离散化需要进行排序去重
- 排序:sort(alls.begin(),alls.end())
- 去重:alls.earse(unique(alls.begin(),alls.end()),alls.end());
unque函数实现
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]) { a[j++] = a[i]; } } return a.begin() + j; }
|
离散化常见题目
给定一个无限长的数轴
输入一个n,执行n次操作即在x的位置上插入一个数c
输入一个m,执行m次操作,每一次操作给出两个数l和r,代表数轴的左右端点
最终打印l和r之间的区间总和
定义数组大小,由于我们插入操作包含在指定下标插入,插入左右端点,所以需要定义N = 300010
我们需要定义三个集合,一个集合用来统计下标,其余两个集合用来对插入的数据进行存储
find函数,由于我们离散化的本质就是通过集合从0开始建立下标代替原本插入值的下标,我们可以通过插入的x找到在集合中的位置,在对应的位置上 += 它的值
接着求数组的前缀和
最终通过a[r] - a[l - 1]
求区间和
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N = 300010; vector<int> alls; vector<PII> a,b; int tmp[N],s[N]; int find(int x) { 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; }
int main(){ int n,m; cin >> n >> m; while(n--) { int x,c; cin >> x >> c; a.push_back({x,c}); alls.push_back(x); } while(m--) { int l,r; cin >> l >> r; b.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 : a) { int t = find(it.first); tmp[t] += it.second; } for(int i = 1;i <= alls.size();i++) s[i] = s[i - 1] + tmp[i]; for(auto it : b) { int rl = find(it.first),rr = find(it.second); cout << s[rr] - s[rl - 1] << endl; } return 0; }
|