离散化

例题

分析

离散化事实上就是当这个数据范围比较大的时候但是能用到的数比较少的时候需要用到的算法。就比如这个题，​a_i 和 ​b_i 的数据范围超大但 ​n 的数据范围只有 ​2\times 10^5。这个时候我们可以将其压缩，使得所有内容之间没有空位。

以样例为例，实现如下图：

压缩后进行排序并去重后离散化数组内部则是 c[]={-1,1,2,5,9,11} 。

然后二分找到每个区间的起始点和对应的重点，反映到离散化 c 数组中，最后进行统一计数即可。总的时间复杂度为 ​O(nlogn) ，排序是这个算法的瓶颈。

代码

#include<bits/stdc++.h>
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x))
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int n,a[N],b[N],c[N],d[N],f[N];
int main(){
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        d[++cnt]=a[i];
        d[++cnt]=b[i];
    }
    sort(d+1,d+1+cnt);
    int cnt2=0;
    for(int i=1;i<=cnt;i++){
        if(d[i]!=d[i-1]||i==1){
            c[++cnt2]=d[i];
        }
    }
    for(int i=1;i<=n;i++){
        int x=lower_bound(c+1,c+1+cnt2,a[i])-c;
        int y=lower_bound(c+1,c+1+cnt2,b[i])-c;
        for(int i=x;i<y;i++){
            f[i]=1;
        }
    }
    int ans=0;
    for(int i=1;i<cnt2;i++){
        if(f[i]==1){
            ans+=c[i+1]-c[i];
        }
    }
    cout<<ans;
    return 0;
}

此文章的图片内部图文内容摘自《洛谷深入浅出程序设计竞赛进阶篇》，其余部分为原创内容。如涉及版权问题请与站长联系。