离散化与区间合并

离散化与区间合并 1.离散化模板离散化问题的性质，整个值域的跨度很大，但是数据非常的稀疏。 123456789101112131415//将所有值排序 并去掉重复元素vector<int> nums;sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());//二分求出x对应的离散化的值int find(int x) {//找到第一个大于等于x的位置 int low = 0, high = nums.size() - 1; while (low < high) { int mid = low + high >> 1; if (nums[mid] >= x) high = mid; else low = mid + 1; } return high + 1;//映射到1, 2, ...n} 2.AcWing802.区间和1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<iostream>#include<algorithm>#include<vector>using namespace std;typedef pair<int, int> PAIR;const int MAX = 300010;int n, m;int a[MAX];int prefix[MAX];vector<int> nums;//离散化数据存储容器vector<PAIR> add, query;//二分求出x对应的离散化的值int find(int x) {//找到第一个大于等于x的位置 int low = 0, high = nums.size() - 1; while (low < high) { int mid ...