P5385 [Cnoi2019] 须臾幻境

· · 题解

:::info[喜提洛谷当前最优解]{open} 原因大概是可持久化线段树维护方式与多数题解有所不同。

https://www.luogu.com.cn/record/227639843 :::

注意到有一个经典的 Trick：连通块数 = 点数 - 生成森林边数。

考虑 LCT 维护生成森林。

为了保证 l\sim r 构成的图一定存在一个生成森林是我们构造的 1\sim r 的生成森林的子图，需要令 1\sim r 的生成森林中边的编号尽可能大。

于是，我们依次添加编号为 1\sim m 的每条边，如果此前已连通则删除二点路径上编号最小的边。

为了维护路径上边的编号的最小值，我们可以使用拆边。新建结点表示该边，并令其点权为边的编号，同时分别与两个端点连边。

询问时，我们只需求出 l\sim r 有多少边在构造的 1\sim r 的生成森林中。使用可持久化线段树维护即可。

注意到每条边都会被加入，为了减小常数，我们直接维护 1\sim r 的删边情况，删掉为 1，不删为 0。

设编号 l\sim r 的边有 c 条不在 1\sim r 的生成森林中。则答案为 n-(r-l+1-c)。

时间复杂度 \mathcal{O}(n+m\log n+(m+q)\log m)，空间复杂度 \mathcal{O}(n+m \log m)。

:::success[[Cnoi2019] 须臾幻境 - P5385.cpp]

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5,maxm=2e5+5;
int root[maxn],tree[maxm<<4],ch[maxn<<4][2];
int sum[maxn],fath[maxn],tag[maxn],val[maxn],son[maxn][2];
int secu[maxm],secv[maxm],n,m,q,t,idx;
inline bool dir(int u){
    return son[fath[u]][1]==u;
}
inline bool isroot(int u){
    return son[fath[u]][0]!=u and son[fath[u]][1]!=u;
}
inline void pushup(int u){
    sum[u]=min(min(sum[son[u][0]],sum[son[u][1]]),val[u]);
}
inline void pushdown(int u){
    if(tag[u]){
        if(son[u][0]){
            tag[son[u][0]]^=1;
            swap(son[son[u][0]][0],son[son[u][0]][1]);
        }
        if(son[u][1]){
            tag[son[u][1]]^=1;
            swap(son[son[u][1]][0],son[son[u][1]][1]);
        }
        tag[u]=0;
    }
}
void update(int u){
    if(!isroot(u)) update(fath[u]);
    pushdown(u);
}
inline void rotate(int u){
    int p=fath[u],g=fath[p],d=dir(u);
    if(!isroot(p)) son[g][dir(p)]=u;
    son[p][d]=son[u][d^1],fath[son[u][d^1]]=p;
    son[u][d^1]=p,fath[p]=u,fath[u]=g;
    pushup(p),pushup(u);
}
inline void splay(int u){
    update(u);
    for(int p=fath[u];!isroot(u);rotate(u),p=fath[u]){
        if(!isroot(p)) rotate(dir(u)==dir(p)?p:u);
    }
}
inline int access(int u){
    int p=0;
    for(;u;p=u,u=fath[u]){
        splay(u),son[u][1]=p,pushup(u);
    }
    return p;
}
inline void makeroot(int u){
    int p=access(u);
    tag[p]^=1;
    swap(son[p][0],son[p][1]);
}
inline int find(int u){
    access(u),splay(u),pushdown(u);
    while(son[u][0]) pushdown(u=son[u][0]);
    splay(u);
    return u;
}
inline void split(int u,int v){
    makeroot(u),access(v),splay(v);
}
inline void link(int u,int v){
    makeroot(u),splay(u),fath[u]=v;
}
inline void cut(int u,int v){
    makeroot(u),access(v),splay(v);
    son[v][0]=fath[u]=0;
    pushup(v);
}
int build(int pos,int val,int p,int pl,int pr){
    int now=++idx;
    if(pl==pr){
        tree[now]=val;
        return now;
    }
    int mid=(pl+pr)>>1;
    if(pos<=mid) ch[now][0]=build(pos,val,ch[p][0],pl,mid),ch[now][1]=ch[p][1];
    else ch[now][1]=build(pos,val,ch[p][1],mid+1,pr),ch[now][0]=ch[p][0];
    tree[now]=tree[ch[now][0]]+tree[ch[now][1]];
    return now;
}
int query(int pos,int p,int pl,int pr){
    if(pos<=pl) return tree[p];
    int mid=(pl+pr)>>1;
    if(pos<=mid) return query(pos,ch[p][0],pl,mid)+tree[ch[p][1]];
    return query(pos,ch[p][1],mid+1,pr);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q>>t;
    for(int i=0;i<=n;++i){
        sum[i]=val[i]=1e9;  
    }
    int tmp,fu,fv;
    for(int i=1;i<=m;++i){
        sum[i+n]=val[i+n]=i;
        cin>>secu[i]>>secv[i];
        if(secu[i]==secv[i]){
            root[i]=build(i,1,root[i-1],1,m);
            continue;
        }
        if(find(secu[i])==find(secv[i])){
            split(secu[i],secv[i]);
            tmp=sum[secv[i]];
            cut(tmp+n,secu[tmp]);
            cut(tmp+n,secv[tmp]);
            root[i]=build(tmp,1,root[i-1],1,m);
        }
        else root[i]=root[i-1];
        link(i+n,secu[i]);
        link(i+n,secv[i]);
    }
    int last=0,l,r;
    for(int i=1;i<=q;++i){
        cin>>l>>r;
        if(t>0){
            l=(l+last)%m+1;
            r=(r+last)%m+1;
        }
        if(l>r) swap(l,r);
        cout<<(last=n-r+l-1+query(l,root[r],1,m))<<"\n";
    }
    return 0;
}

:::