离散化的核心思想

初学离散化，上来没理解，看了带佬的题解，二刷视频，有了一点想法

离散化针对的问题：值域大，但是个数很少，整体上显得稀疏，有时候，这个值域也是数组下标/下标标志
为啥说下标标志更准确呢，像下面例题，可能插入的下标是负数，而数组下标大于等于0，不能这样说。

我们要做的是，把这些用到的 所有下标标志  一一映射  下标从0（或1）开始的数组中
映射：实际上就是把所有下标标志按顺序放入到数组中去，把数组的下标，作为所有下标标志离散化的最终结果

• 两个问题

alls[]可能会有重复的元素，怎么办？去重

alls[]:存放所有下标标志的数组
去重的方式：
vector<int> alls;                                       //存放所有待离散化的值
sort(alls.begin(),alls.end());                          //将待离散化的值排序
alls.erase(unique.(alls.begin(),alls.end()),alls.end());

// unique(alls.begin(),all.end())  去除所有的重复元素，返回去重之后数组的最后一个元素的下标 ii
// alls.erase(ii,alls.end());      删除末尾的重复的所有的数组元素

如何算出待离散化的值 经过离散化处理以后 在alls[]数组中存放的下标？ 整数二分

x:x是待离散化的数值
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;                
    //这里返回r还是返回r+1 ，要具体问题具体分析，因为此题用前缀和处理，从1开始不用考虑边界问题
}

实例：区间和

问题

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

空间分析

一共需要
n次操作：  n个下标    x
m次查询： 2m个下标    l r  

const int N=n+2m=3e5;   

代码

#include <iostream>
#include <vector>
#include <algorithm>       //算法库
using namespace std;
int n,m;
const int N=300010; 
typedef pair<int,int> PII; //pair 提供一个包含2个数据成员的结构体模板 
                           //通过first，second访问2个成员
vector<int> alls;          //存放待离散化的值
vector<PII> add,query;     //存放两种操作（相加x c 查询l r）的参数

int a[N],s[N];            

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<n;i++)
    {
        int x,c; cin>>x>>c;
        alls.push_back(x);       //将待离散化的下标标志放入alls[]
        add.push_back({x,c});    //将相加参数x c放入 add[] 
    }

    for(int j=0;j<m;j++)
    {
        int l,r; cin>>l>>r;
        alls.push_back(l);        
        alls.push_back(r);       //将待离散化的下标标志放入alls[]
        query.push_back({l,r});  //将查询参数l r放入 query[]
    }

    //对adds[] 去重
    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;          //把c加上
    }

    //构造前缀和
    //循环的终止条件是否应该是i<=a[x].size()  ???错误
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];


    //处理查询
    for(auto item:query)
    {
        int l=find(item.first);  
        int r=find(item.second);   //获取离散化之后的下标
        cout<<s[r]-s[l-1]<<endl;
    }
}

• 一点疑问

//构造前缀和
//循环的终止条件是否应该是i<=a[x].size()  ???错误
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];

这里循环终止条件为什么是i<=alls.size(),如图所示

数组alls  存储的是下标标志（包括插入操作下标 查询操作下标）  存入→排序→去重
数组a[]   存储的是下标标志插入的值

alls.size()在此例子中是最大的那个待离散化的下标标志 经离散化后 对应的数组的下标 也就是6
所以构造前缀和要构造到最后一个插入元素下标 或者 询问的下标