值域大，个数小

两个问题

  1. 重复元素 > 去重
  2. 快速映射 > 二分

模板

  1. vector<int> alls; // 存储所有待离散化的值
  2. sort(alls.begin(), alls.end()); // 将所有值排序
  3. alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
  5. // 二分求出x对应的离散化的值
  6. int find(int x) // 找到第一个大于等于x的位置
  7. {
  8.     int l = 0, r = alls.size() - 1;
  9.     while (l < r)
  10.     {
  11.         int mid = l + r >> 1;
  12.         if (alls[mid] >= x) r = mid;
  13.         else l = mid + 1;
  14.     }
  15.     return r + 1; // 映射到1, 2, ...n
  16. }

运用

  1. //离散化，让大的数变成小的
  2. //用vector储存大的数，然后处理大的数a的时候，在vector中找到a，返回vector的下标x
  3. //在定义一个数组，a => x;处理a[x]即可
  5. #include <iostream>
  6. #include <cstring>
  7. #include <algorithm>
  8. #include <vector>
  10. using namespace std;
  12. typedef long long LL;
  13. typedef pair<int,int> PII;
  16. vector<int> alls;
  18. vector<PII> add,query;
  19. int a[300010],s[300010];
  21. int find(int x)  // 找到x 
  22. {
  23.     int l= 0,r=alls.size()-1;
  24.     while(l<r)
  25.     {
  26.         int mid = l+r >> 1;
  27.         if(alls[mid]>=x) r=mid; //找x的最左边 
  28.         else l=mid+1;
  29.     }
  30.     return r+1; // 方便前缀和
  31. }
  34. int main()
  35. {
  36.     int n,m;
  37.     cin>>n>>m; 
  38.     for(int i=0;i<n;i++)
  39.     {
  40.         int x,c;
  41.         cin>>x>>c;
  42.         add.push_back({x,c});
  44.         alls.push_back(x);   
  45.     } 
  46.     for(int i=0;i<m;i++)
  47.     {
  48.         int l,r;
  49.         cin>>l>>r;
  50.         query.push_back({l,r});
  52.         alls.push_back(l);
  53.         alls.push_back(r);
  55.     }
  56.     //排序 
  57.     sort(alls.begin(),alls.end());
  58.     //去重
  59.     alls.erase(unique(alls.begin(),alls.end()),alls.end());
  61.     //处理插入
  62.     for(auto item : add)
  63.     {
  64.       int x=  find(item.first);
  65.       a[x] += item.second;
  66.     }
  67.     //预处理前缀和
  68.     for(int i=1;i<= alls.size();i++) s[i]=s[i-1]+a[i];
  70.     //处理询问
  71.     for(auto item : query)
  72.     {
  73.         int l = find(item.first);
  74.         int r = find(item.second);
  76.         cout<<s[r]-s[l-1]<<endl;
  77.     }
  79.     return 0;
  80. }

区间合并

image.png

  1. // 将所有存在交集的区间合并
  2. void merge(vector<PII> &segs)
  3. {
  4.     vector<PII> res; //先定义一个新的PII
  6.     sort(segs.begin(), segs.end());  //对于pair的排序，先按first，若相等，再按second；
  8.     int st = -2e9, ed = -2e9;
  9.     for (auto seg : segs) // 新的区间，分开的
  10.         if (ed < seg.first) 
  11.         {
  12.             if (st != -2e9) res.push_back({st, ed});
  13.             st = seg.first, ed = seg.second;
  14.         }
  15.         else ed = max(ed, seg.second); //有相交的
  17.     if (st != -2e9) res.push_back({st, ed}); //再把第13行的放进去
  19.     segs = res; //更新
  20. }