十大ppt模板免费下载网站,惠州网络营销,太仓住房和城乡建设局网站,wordpress简单吗离散化是将大范围的数字映射到小范围的区间内#xff0c;适用于稀疏的区间。
两个问题需要考虑#xff1a;
1. 原数组中可能有重复元素#xff0c;需要去重。
2. 如何算出离散化后的值#xff08;离散化后保序#xff0c;使用二分#xff09;。 题目链接#xff1a; …离散化是将大范围的数字映射到小范围的区间内适用于稀疏的区间。
两个问题需要考虑
1. 原数组中可能有重复元素需要去重。
2. 如何算出离散化后的值离散化后保序使用二分。 题目链接
https://www.acwing.com/problem/content/804/
代码
#include iostream
#include vector
#include algorithmusing namespace std;typedef pairint, int PII;const int N 300010;int n, m;
int a[N], s[N];vectorint alls;
vectorPII add, query;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()
{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 find(item.first);a[x] item.second;}// 预处理前缀和for (int i 1; i alls.size(); i) s[i] s[i - 1] a[i];// 处理询问for (auto item : query){int l find(item.first), r find(item.second);cout s[r] - s[l - 1] endl;}return 0;
}
其中unique(alls.begin(), alls.end())将数组中的所有重复元素去重返回去重后的数组的尾端点。使用Java和Python的小伙伴可以使用下列自己实现的方法替换双指针算法
vectorint::iterator unique(vectorint a)
{int j 0;for (int i 0; i a.size(); i)if (!i || a[i] ! a[i - 1])a[j] a[i];// a[0] ~ a[j - 1] 所有a中不重复的数return a.begin() j;
}
