离散化是将大范围的数字映射到小范围的区间内,适用于稀疏的区间。
两个问题需要考虑:
1. 原数组中可能有重复元素,需要去重。
2. 如何算出离散化后的值(离散化后保序,使用二分)。
题目链接:
https://www.acwing.com/problem/content/804/
代码:
#include #include #include using namespace std; typedef pairint, int> PII; const int N = 300010; int n, m; int a[N], s[N]; vectorint> alls; vector 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 ) { int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x); } for (int i = 0; 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 1] + a[i]; // 处理询问 for (auto item : query) { int l = find(item.first), r = find(item.second); cout 1] endl; } return 0; }
其中,unique(alls.begin(), alls.end())将数组中的所有重复元素去重,返回去重后的数组的尾端点。使用Java和Python的小伙伴可以使用下列自己实现的方法替换(双指针算法):
vectorint>::iterator unique(vectorint>& a) { int j = 0; for (int i = 0; i ) if (!i || a[i] != a[i - 1]) a[j++] = a[i]; // a[0] ~ a[j - 1] 所有a中不重复的数 return a.begin() + j; }
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net