线段树区间离散化维护按秩合并并查集（可撤销）——牛客多校第八场E

谁借莪１个温暖的怀抱￠ 2023-10-11 09:14 7阅读 0赞

模板题。。去网上学了可撤销的并查集。。

/* 给定一个无向图，边的属性为(u,v,l,r),表示<u,v>可以通过的size为[l,r] 求出有多少不同的size可以从1->n 把每条边的范围[l,r]进行区间离散化然后 建立线段树，然后把每条边按范围更新进线段树里 对线段树进行dfs，同时维护一个可撤销的并查集，经过每个线段树结点都用结点里存的边去更新并查集 到了叶子结点，如果发现[1,n]在同一个集合里，说明联通，那么把这个区间的贡献算上 回溯时要对并查集进行撤销 */
    #include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    #define maxn 200005
    typedef pair<int,int>pii;
    struct Edge{
        int u,v,l,r;}e[maxn];
    int n,m,x[maxn],tot,ans;
     
    stack<pii>stk;//合并操作栈
    int F[maxn],size[maxn];
    int find(int x){
        //这里不能路径压缩
        return F[x]==x?x:find(F[x]);
    }
    void bing(int x,int y){
        int f1=find(x),f2=find(y);
        if(f1==f2)//压入无效操作
            stk.push(make_pair(-1,-1));
        else {
        //把f2并入f1
            if(size[f1]<size[f2])swap(f1,f2);
            size[f1]+=size[f2];
            F[f2]=f1;
            stk.push(make_pair(f1,f2));
        }
    }
    void cancle(){
        pii t=stk.top();stk.pop();
        if(t.first==-1 && t.second==-1)return;
        size[t.first]-=size[t.second];
        F[t.second]=t.second;
        return;
    }
     
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    vector<int>seg[maxn<<2];
    void update(int L,int R,int id,int l,int r,int rt){
        if(L<=l && R>=r){seg[rt].push_back(id);return;}
        int m=l+r>>1;
        if(L<=m)update(L,R,id,lson);
        if(R>m)update(L,R,id,rson);
    }
    void query(int l,int r,int rt){
        for(int i=0;i<seg[rt].size();i++){
            int j=seg[rt][i];
            bing(e[j].u,e[j].v);
        }
        if(l==r){
            if(find(1)==find(n))
                ans+=x[l+1]-x[l];
            for(int i=0;i<seg[rt].size();i++)cancle();
            return;
        }
        int m=l+r>>1;
        query(lson);query(rson);
        for(int i=0;i<seg[rt].size();i++)cancle();
    }
     
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)   
            scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].r);
        for(int i=1;i<=m;i++){
            x[++tot]=e[i].l;
            x[++tot]=++e[i].r;
        }
        sort(x+1,x+1+tot);
        tot=unique(x+1,x+1+tot)-x-1;
         
        for(int i=1;i<=m;i++){
            int posl=lower_bound(x+1,x+1+tot,e[i].l)-x;
            int posr=lower_bound(x+1,x+1+tot,e[i].r)-x;posr--;
            update(posl,posr,i,1,tot,1);
        }
         
        for(int i=1;i<=n;i++)F[i]=i;
        for(int i=1;i<=n;i++)size[i]=1;
        query(1,tot,1);
        cout<<ans<<'\n';
    }

下面是比较简洁的代码

#include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    #define maxn 400005
    typedef pair<int,int>pii; 
    
    int n,m,x[maxn],tot;
    long long ans;
    int u[maxn],v[maxn],L[maxn],R[maxn],num[maxn];
    
    stack<pii>stk;//合并操作栈 
    int fa[maxn],sz[maxn];
    int find(int x){
        //这里不能路径压缩 
        return fa[x]==x?x:find(fa[x]);
    } 
    void bing(int x,int y){
        int f1=find(x),f2=find(y);
        if(f1==f2)//压入无效操作 
            stk.push(make_pair(-1,-1));
        else {
        //把f2并入f1 
            if(sz[f1]<sz[f2])swap(f1,f2);
            sz[f1]+=sz[f2];
            fa[f2]=f1;
            stk.push(make_pair(f1,f2)); 
        }
    }
    void cancel(){
        pii t=stk.top();stk.pop();
        if(t.first==-1 && t.second==-1)return;
        sz[t.first]-=sz[t.second];
        fa[t.second]=t.second;
    }
    
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    vector<int>seg[maxn<<2];
    void update(int L,int R,int id,int l,int r,int rt){
        if(L<=l && R>=r){seg[rt].push_back(id);return;}
        int m=l+r>>1;
        if(L<=m)update(L,R,id,lson);
        if(R>m)update(L,R,id,rson);
    }
    void query(int l,int r,int rt){
        for(int i=0;i<seg[rt].size();i++){
            int j=seg[rt][i];
            bing(u[j],v[j]);
        }
        if(l==r){
            if(find(1)==find(n))
                ans+=num[l+1]-num[l];
            for(int i=0;i<seg[rt].size();i++)cancel();
            return;
        }
        int m=l+r>>1;
        query(lson);query(rson);
        for(int i=0;i<seg[rt].size();i++)cancel();
    }
    int main(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>u[i]>>v[i]>>L[i]>>R[i];
            num[++tot]=L[i];
            num[++tot]=++R[i];
        }
        sort(num+1,num+1+tot);
        tot=unique(num+1,num+1+tot)-num-1;
        
        for(int i=1;i<=m;i++){
            int posl=lower_bound(num+1,num+1+tot,L[i])-num;
            int posr=lower_bound(num+1,num+1+tot,R[i])-num-1;
            update(posl,posr,i,1,tot-1,1);
        }
        for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
        query(1,tot-1,1);
        cout<<ans<<endl;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11335570.html