线性并查集

· · 个人记录

这个东西可以帮助我们严格 O(n) 地解决区间染色问题,属实一大利器。

例题：给定长度为 n 序列 ，每次覆盖区间 [l,r] 然后让你求出最后可以看到几个颜色。

并查集，线段树，这些东西都是 \text {O(nlogn)} 的,然后我们有个严格 O(n) 的做法。

我们可以对原序列分成 log(n) 大小个块，然后从后向前去扫区间，然后如果说这个块内所有元素已经全部被覆盖，那么我们就要去指向下一个块，否则我们就要一步一步地去将这个区间 lowbit 染色，因为每个点最多被覆盖一次，所以说复杂度为 O(n)。

例题 ：P3740 。但由于这题离散化带个 log , 所以并没有实质性的优化。

代码写的很丑。

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=4e3+5;
int n,m,belong[maxn],block,num,cun[maxn],cnt,c[maxn],ans; 
struct hb{int l,r;}a[maxn];
struct bl{int l,r,db,f;}kuai[maxn];
bool vis[maxn];
int findf(int i){return kuai[i].f==i?i:kuai[i].f=findf(kuai[i].f);}
void build(){
    block=(int)__lg(n);
    num=(n/block);
    if(n%block) num++; 
    for(int i=1;i<=n;++i) belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;++i){
        kuai[i].l=(i-1)*block+1;
        kuai[i].r=min(n,i*block);
        kuai[i].db=(1<<(kuai[i].r-kuai[i].l+1))-1;
        kuai[i].f=i;
    }
}
void update(int ql,int qr,int color){
    if(belong[ql]==belong[qr]){ 
        int sy=belong[ql];
        int ll=kuai[sy].l,rr=kuai[sy].r;
        int now=(1<<(qr-ll+1))-(1<<(ql-ll));
        int rest=(1<<(rr-ll+1))-1;
        rest=rest^now;
        now&=kuai[sy].db;
        kuai[sy].db&=rest;//仅保留剩下的部分 
        while(now){
            int x=lowbit(now);
            c[(int)__lg(x)+kuai[sy].l]=color;
            now-=x;
        }
        if(!kuai[sy].db) kuai[sy].f=sy+1;
    }
    else{
        int lb=belong[ql],rb=belong[qr];
        int now=((1<<(kuai[lb].r-kuai[lb].l+1))-(1<<(ql-kuai[lb].l)));
        int rest=(1<<(kuai[lb].r-kuai[lb].l+1))-1;
        rest=rest^now;
        now&=kuai[lb].db;
        kuai[lb].db&=rest;//仅仅保留剩下的部分 
        while(now){
            int x=lowbit(now);
            c[(int)__lg(x)+kuai[lb].l]=color;
            now-=x;
        }
        if(!kuai[lb].db) kuai[lb].f=lb+1;
        for(int i=lb+1;i<rb&&i;i=findf(i)){
            while(kuai[i].db){
                int x=lowbit(kuai[i].db);
                c[(int)__lg(x)+kuai[i].l]=color;
                kuai[i].db-=x;
            }
            kuai[i].f=i+1;
        }//表示整块的处理 
        now=(1<<(qr-kuai[rb].l+1))-1;
        rest=(1<<(kuai[rb].r-kuai[rb].l+1))-1;
        rest^=now;
        now&=kuai[rb].db;
        kuai[rb].db&=rest;
        while(now){
            int x=lowbit(now);
            c[(int)__lg(x)+kuai[rb].l]=color;
            now-=x;
        } 
        if(!kuai[rb].db) kuai[rb].f=rb+1; 
    }
} 
int sd[maxn];//sd 所代表的 因为中间可能有空格 这些空格会对答案产生影响
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>a[i].l>>a[i].r;
        cun[++cnt]=a[i].l;
        cun[++cnt]=a[i].r;
    }
    sort(cun+1,cun+cnt+1);
    cnt=unique(cun+1,cun+cnt+1)-cun-1;
    sd[1]=1;
    for(int i=2;i<=cnt;++i){
        sd[i]++;
        if(cun[i]>cun[i-1]+1) sd[i]++; 
    }
    for(int i=1;i<=cnt;++i) sd[i]+=sd[i-1];
    n=0;
    for(int i=1;i<=m;++i){
        a[i].l=sd[lower_bound(cun+1,cun+cnt+1,a[i].l)-cun];
        a[i].r=sd[lower_bound(cun+1,cun+cnt+1,a[i].r)-cun];
        n=max(n,a[i].r);
    }
    build();
    for(int i=m;i;i--) update(a[i].l,a[i].r,i); 
    for(int i=1;i<=n;++i){
        if((!vis[c[i]])&&c[i]) {
            vis[c[i]]=1;
            ans++;
        } 
    }
    printf("%d\n",ans);
    return 0;
}