差分与离散化

离散化的使用场景：数的范围很大，但实际上用的较少，数之间的间隔比较大。

Map写法

• 代码短，容易实现
• 效率低

Map的使用，简洁直接的实现了映射关系

1 定义map

map<int,int> b;

2 map通过key找value

b[l] += value;
b[r+1] -= value;

3 前缀和恢复具体某一点的值

3.1 朴素版本

  b[i] +=b[i-1];

3.2 离散化版本

  int res = 0, sum =0
  for(auto& [key,value]:b)
  {
      sum += value;
      res = max(res,sum);
  }

手写离散化

• 代码长，出错概率变大
• 效率高

思路：

1. vector存储
2. 排序
3. 去重
4. 映射的部分，由Map变成对有序vector的二分

1 vector存储

vector<int> xs;

2 把区间端点放入

xs.push_back(); 

3 排序

sort(xs.begin(),xs.end());

4 去重

xs.erase(unique(xs.begin(),xs.end()),xs.end());

5 find 实现 映射

映射之后的范围即是vector的大小

int find(int v)
{
    int l = 0, r = xs.size()-1;

    while(l<r)
    {
        int mid = l+r>>1;
        if(xs[mid]>=v) r = mid;
        else l = mid+1;
    }
    return r;
}