【洛谷P5385】[Cnoi2019]须臾幻境 | Mrsrz's blog

LCT+可持久化线段树

题目大意：

给定一张 $n$ 个点，$m$ 条边的无向图，每条边有编号。

多组询问，每次询问只保留编号为 $l\sim r$ 的边所能形成的连通块的个数。

强制在线。

题解：

我们按编号从小到大加边，用 LCT 维护当前的图。

对每条边 $i$，如果加入的时候形成了环，那么我们把这个环上加入时间最早的边 $k$ 删掉，并记录边 $i$ 替换掉的边 $h_i=k$。如果没替换边则 $h_i=0$。

考虑查询的时候，我们查询 $[l,r]$ 内 $h_i\in[0,l-1]$ 的 $i$ 的个数 $c$，然后 $n-c$ 即为答案。

我们考虑一条新加入的边，如果这条边原定要替换的边不存在，或者在 $l$ 之前，那么加入这条边的时候，势必会将两个连通块合并，所以贡献 $-1$。如果要替换的边在 $[l,r]$ 内，则之前的那条边已经将两个连通块连通，这条边就不计贡献。

用 LCT 预处理出 $h_i$，然后用可持久化线段树维护、查询即可。

注意自环要判掉。

时间复杂度 $O((n+m+q)\log n)$。

Code：

#include<iostream>
#include<algorithm>
#include<utility>
using namespace std;
const int N=3e5+6,inf=1e9;
int n,m,q,t;
pair<int,int>e[N];
namespace lct{
    int sz[N],fa[N],ch[N][2],val[N],mn[N];bool tag[N];
    inline bool ckr(int x,const int p=1){return ch[fa[x]][p]==x;}
    inline bool isroot(int x){return!(ckr(x)||ckr(x,0));}
    inline void flip(int x){swap(ch[x][0],ch[x][1]),tag[x]^=1;}
    inline void update(int x){
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
        mn[x]=min({mn[ch[x][0]],mn[ch[x][1]],val[x]});
    }
    inline void pushdown(int x){
        if(tag[x]){
            tag[x]=0;
            if(ch[x][0])flip(ch[x][0]);
            if(ch[x][1])flip(ch[x][1]);
        }
    }
    inline void rotate(int x){
        int y=fa[x],z=fa[y],k=ckr(x);
        if(!isroot(y))ch[z][ckr(y)]=x;
        fa[y]=x,fa[x]=z,fa[ch[x][!k]]=y;
        ch[y][k]=ch[x][!k],ch[x][!k]=y;
        update(y);
    }
    inline void splay(int x){
        static int sta[N],top;sta[top=1]=x;
        for(int y=x;!isroot(y);sta[++top]=y=fa[y]);
        while(top)pushdown(sta[top--]);
        for(;!isroot(x);rotate(x))
            if(!isroot(fa[x]))rotate((ckr(x)^ckr(fa[x]))?x:fa[x]);
        update(x);
    }
    inline void access(int x){for(int y=0;x;ch[x][1]=y,y=x,x=fa[x])splay(x);}
    inline void makeroot(int x){access(x),splay(x),flip(x);}
    inline void split(int x,int y){makeroot(x),access(y),splay(y);}
    inline int findroot(int x){access(x);for(splay(x);ch[x][0];x=ch[x][0]);splay(x);return x;}
    inline bool connect(int x,int y){return findroot(x)==findroot(y);}
    inline void link(int x,int y){makeroot(x),fa[x]=y;}
    inline void cut(int x,int y){split(x,y);if(ch[y][0]==x&&sz[y]==2)fa[x]=ch[y][0]=0,update(y);}
    int deledge(int x,int y){
        split(x,y);
        int id=mn[y];
        int a=e[id].first,b=e[id].second,d=n+id;
        cut(a,d),cut(b,d);
        return id;
    }
    void addedge(int x,int y,int id){
        int d=n+id;
        lct::sz[d]=1;
        lct::val[d]=lct::mn[d]=id;
        link(x,d),link(y,d);
    }
}
namespace sgt{
    int rt[N],ls[N*100],rs[N*100],sz[N*100],nod=0;
    void insert(int&o,int pre,int l,int r,const int&val){
        sz[o=++nod]=sz[pre]+1;
        if(l<r){
            const int mid=l+r>>1;
            if(val<=mid)
                insert(ls[o],ls[pre],l,mid,val),rs[o]=rs[pre];
            else
                insert(rs[o],rs[pre],mid+1,r,val),ls[o]=ls[pre];
        }
    }
    void add(int nw,int pre,int x){insert(rt[nw],rt[pre],0,m,x);}
    int query(int o,int pre,int l,int r,const int&L,const int&R){
        if(!o&&!pre)return 0;
        if(L<=l&&r<=R)return sz[o]-sz[pre];
        const int mid=l+r>>1;
        if(L<=mid&&mid<R)return query(ls[o],ls[pre],l,mid,L,R)+query(rs[o],rs[pre],mid+1,r,L,R);
        if(L<=mid)return query(ls[o],ls[pre],l,mid,L,R);return query(rs[o],rs[pre],mid+1,r,L,R);
    }
    int ask(int l,int r,int L,int R){return query(rt[r],rt[l-1],0,m,L,R);}
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q>>t;
    lct::mn[0]=lct::val[0]=inf;
    for(int i=1;i<=n;++i)lct::mn[i]=lct::val[i]=inf,lct::sz[i]=1;
    for(int i=1;i<=m;++i){
        int x,y;
        cin>>x>>y;
        e[i]=make_pair(x,y);
        if(x!=y&&lct::connect(x,y)){
            int pr=lct::deledge(x,y);
            sgt::add(i,i-1,pr);
        }else
            if(x!=y)
                sgt::add(i,i-1,0);
            else
                sgt::rt[i]=sgt::rt[i-1];
        if(x!=y)
        lct::addedge(x,y,i);
    }
    int ans=0;
    while(q--){
        int l,r;
        cin>>l>>r;
        if(t)
            l=(l+ans)%m+1,r=(r+ans)%m+1;
        if(l>r)swap(l,r);
        ans=n-sgt::ask(l,r,0,l-1);
        cout<<ans<<'\n';
    }
    return 0;
}