CHiCO酱の离散化笔记

· · 个人记录

离散化在OI中是一个比较常用的算法，有许多题目都需要进行离散化。

写这篇学习笔记的原因是在机房某dalao竟然不会离散化！震惊CHiCO一整年。

Part1. 离散化的应用地点

像是一些看似数据范围很大，实际上所需要使用的数据却不会特别多的题目便可以使用离散化来解决。

一道例题。

我们可以看到此题的a,b的数据范围很大，但实际对我们有用的数据个数（2n个）却不算多。这时我们可以运用离散化进行解决。

Part2. 离散化的核心代码

其实就只有三个部分。。。

是不是很简单

  1. 排序 就一个sort就可以弄好了。。。当然，你也可以自己写。不过我一直都不会写排序算法所以就不写了。

    sort(a+1,a+n+1);

  2. 去重 algorithm库里面有帮你去重的函数，名为unique。可以了解一下它的用法。当然，你同样还可以自己写。不过我很懒所以就不写了。

    tmp=unique(a+1,a+n+1)-a-1;//因为返回的是指针，所以要-a-1。tmp是排完序后数组的长度

  3. 查找原来某一个数离散化后的值是多少 离散化之后的值其实是自己在整个数列中的排名。要想快速找到某个数在数列中的排名，最好的选择便是O(logn)的二分查找。你可以使用lower_bound函数，也可以自己写二分。不过我二分经常写错所以就不写了。

    inline int Get(int val){
    return lower_bound(a+1,a+tmp+1,val)-a;
}

所有的离散化操作就学完了。的确很简单对不。

一定要学好STL啊。

Part3. 离散化的实际应用

前面bb了那么多，还是要应用一下下的。

P1496

一道模板题了。

我们可以发现数据范围大，但是实际需要的范围并没有那么大，我们就可以考虑使用离散化。剩下的直接模拟就可以了。

#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+10;
struct node{
    int x,y;
};
node q[N];
int a[N];
bool vis[N];
int t,tmp;
inline int Get(int val){
    return lower_bound(a+1,a+tmp+1,val)-a;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q[i].x>>q[i].y;
        a[++t]=q[i].x;
        a[++t]=q[i].y;
        //注意离散化要记录原来的问题 
    }
    sort(a+1,a+t+1);
    tmp=unique(a+1,a+t+1)-a-1;
    int x,y;
    for(int i=1;i<=n;i++){
        x=Get(q[i].x);
        y=Get(q[i].y);
        //找到离散化之后的值 
        for(int j=x;j<y;j++)//注意要小于y 
            vis[j]=true;//暴力为这一段区间打上标记 
    }
    long long ans=0;
    for(int i=1;i<=tmp;i++)
        if(vis[i])
            ans+=a[i+1]-a[i];//统计答案 
    cout<<ans;
}

P1955

一看就可以知道是并查集的题目了。

但是有个问题就是i,j的范围很大，到了10^9，但实际上使用的个数只有n个。所以我们应该要使用离散化来进行处理。

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+10;
struct node{
    int x,y,e;
};
node q[N];
int a[N],fa[N];
int t,tmp;
inline bool cmp(node x,node y){
    return x.e>y.e;
}
void clear(){
    memset(a,0,sizeof a);
    memset(q,0,sizeof q);
    memset(fa,0,sizeof fa);
    t=0;
    tmp=0;
}
inline int Get(int val){
    return lower_bound(a+1,a+tmp+1,val)-a;
}
inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
    if(x!=y)
        fa[x]=y;
}
int main(){
    int k;
    cin>>k;
    while(k--){
        clear();
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>q[i].x>>q[i].y>>q[i].e;
            a[++t]=q[i].x;
            a[++t]=q[i].y;
        }
        sort(a+1,a+t+1);
        sort(q+1,q+n+1,cmp);//注意q要按照问题进行排序
        tmp=unique(a+1,a+t+1)-a-1;
        for(int i=1;i<=tmp;i++)
            fa[i]=i;
        int x,y;
        int fx,fy;
        bool flag=false;
        for(int i=1;i<=n;i++){
            x=Get(q[i].x);
            y=Get(q[i].y);
            fx=find(x);
            fy=find(y);
            if(q[i].e)
                merge(fx,fy);
            else
                if(fx==fy){
                    cout<<"NO\n";
                    flag=true;
                    break;
                }
        }
        if(!flag)
            cout<<"YES\n";
    }
}

Part4. 离散化的总结

首先要声明离散化是离线算法，如果有毒瘤出题人恶意强制在线（即为给出的数据是加密过的，需要处理（常为异或上lastans），而不知道实际的值为什么，无法进行离散化处理），那么果断放弃离散化加其他东西乱搞吧。

离散化是许多高级数据结构的基础，像是权值线段树、主席树、扫描线之类的东西都是需要离散化缩小范围再进行使用的。

所有值域大但有用数据小的题目都要优先考虑离散化。

有些题目会先让你离散化之后再套一些数据结构来做。

总之离散化是非常重要的东西，一定要学会它。

Part5. 离散化的习题

既然都讲了离散化，怎么可以不写写习题呢。

P3740 离散化值域之后再进行线段树区间修改，要注意一些小问题。

P5937 同样是离散化加并查集，但是要使用到并查集的扩展域或边带权。不会的可以戳这里。