离散化

把下标非常大的序列映射成下标比较小的序列，并保证离散前后都是相对有序。有点压缩映射的意味在里面。使得映射后的序列非常的不稀疏！！！离散化的本质是映射，可以减少对空间的需求，减少离散化

做离散化的话 使用vector比较方便

思路：数组序列 排序+去重+二分

// 排序+去重
vector<int> alls; // 存储等待离散化的序列
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end()) // unique(alls.begin(),alls.end()) 返回的是已经去重后的子序列的尾结点

比如 长的数组 一般是映射到从1开始的自然数

离散化的概念比较简单，但是不好使用

去重unique轮子

// c++ unique函数的实现 本去重函数只能在排序后使用
vector<int> ::iterator unique(vector<int> &a){
  int j = 0;
  for(int i = 0; i<a.size();i++){
    if(!i || a[i]!=a[i-1]) // 第一个元素一定存起来
      a[j++] = a[i];
  }
  return a.begin()+j;
}

区间和案例：
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
这是一道区间和问题按理说应该使用前缀和的思想，但是麻烦是，本题数轴是无限长，若要开一个级别的数组显然做不到，而且每个值得大小也是级别。于是需要用到离散化的思想【个人觉得就是投影到小数组中】

离散化过程

// 本题表面上是个区间和问题，但是实际中由于初始空间的范围是无限数轴，需要先使用离散化的思想，再进行前缀和求区间和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 10e5+10;

int n,m;
int a[N],s[N]; // a储存的是值，s储存的是前缀和
vector<int> all; // all储存的是所有的下标
vector<pair<int,int>> add,query; // 储存的是添加[index,value] 和 [index1,index2]


int find(int x) { //返回的是输入的坐标的离散化下标
    int l = 0, r = all.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (all[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;   // 保证下标从1开始
}



int main(){
    
    // 1.前期 将需要的数据输入到合适的数组中
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c}); // 将组合对{x,c}传入add
        all.push_back(x);     // all储存的是全部的下标
    }  
    
    for(int i = 0;i<m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        query.push_back({l,r});
        all.push_back(l);
        all.push_back(r);
    }
    
    
    // 2.排序 去重
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    
    for(auto item:add){
        int x = find(item.first);    // 这一段是灵魂代码  只是找到连续的下标
        a[x] += item.second;
    }
    
    // 3.前缀和    预处理 已经保证下标从1开始了
    for(int i = 1;i<=all.size();i++) s[i] = s[i-1] + a[i];
    
    for(auto item:query){
        int l = item.first;
        int r = item.second;
        printf("%d\n",s[r] - s[l-1]);
    }
    
    
    return 0;
}