来自蒟蒻 \(Hero \_of \_Someone\) 的 \(LCT\) 学习笔记
$
$
又是一道骚题......
先讲一个结论:
假设我们用 \(LCT\) 来做这道题, 在插入边 \(i\) 的时候如果遇到了环, 则将环上最早加入的那条边删掉, 并插入边 \(i\),
记 \(cnm [i]\) 为被删除边的编号, 如果插入边 \(i\) 时没有遇到环, 则记 \(cnm[i]=0\).
那么, 每一个询问的答案即为, \(n\ -\ [l,r]中小于\ l\ 的\ cnm[i]\ 的个数\).
$
$
证明:
假设加入边 \(i\) 后形成的的环上没有 \(i\) 和 \(cnm[i]\) 这两条边, 那么这个环将变成两个连通块,
而在加入 \(i\) 且 \(cnm[i]<l\) (即在该询问中, \(cnm[i]\) 并不存在于图中)时, 这两个连通块变成了一个连通块, 即连通块数量 \(-1\) ,
所以 \([l,r]\) 中小于 \(l\) 的 \(cnm[i]\) 的个数即为减少的连通块数量, 得证.
$
$
所以这道题的做法就出来了, 用 \(LCT\) 来求 \(cnm[]\) , 主席树或者树套树维护 \([l,r]\) 中小于 \(l\) 的 \(cnm[i]\) 的个数
$
$
//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define N (400010)
#define RG register
using namespace std;
inline int gi(){ RG int x=0,q=1; RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') q=-1,ch=getchar(); while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar(); return q*x; }
void File(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
int n,m,k,type,cnm[N];
struct Edge{int u,v;}E[N],e[N];
//------------ lct -----------------------------
int ch[N][2],fa[N],rev[N];
int val[N],Min[N];
inline void cur(int x,int y){ val[x]=Min[x]=y; }
inline void up(int x){
Min[x]=min(Min[ch[x][0]],Min[ch[x][1]]);
Min[x]=min(Min[x],val[x]);
}
inline void reverse(int x){
if(!x) return ;
swap(ch[x][0],ch[x][1]);
rev[x]^=1;
}
inline void down(int x){
if(!rev[x]) return ;
reverse(ch[x][0]);
reverse(ch[x][1]);
rev[x]=0;
}
inline bool is_root(int x){ return ch[fa[x]][0]!=x && x!=ch[fa[x]][1]; }
inline bool lr(int x){ return x==ch[fa[x]][1]; }
inline void rotate(int x){
RG int y=fa[x],z=fa[y],k=lr(x);
if(!is_root(y)) ch[z][lr(y)]=x;
fa[x]=z; fa[ch[x][k^1]]=y; fa[y]=x;
ch[y][k]=ch[x][k^1]; ch[x][k^1]=y;
up(y); up(x);
}
int st[N];
inline void splay(int x){
RG int y=x,top=0;
while(1){
st[++top]=y;
if(is_root(y)) break;
y=fa[y];
}
for(RG int i=top;i;i--) down(st[i]);
while(!is_root(x)){
if(!is_root(fa[x])) rotate(lr(x)^lr(fa[x])?x:fa[x]);
rotate(x);
}
}
inline void access(int x){
RG int y=0;
while(x){ splay(x);
ch[x][1]=y; fa[y]=x;
up(x); y=x; x=fa[x];
}
}
inline void make_root(int x){
access(x); splay(x); reverse(x);
}
inline int query(int x,int y){
make_root(x); access(y); splay(y);
return Min[y];
}
inline int find(int x){
while(fa[x]) x=fa[x];
return x;
}
inline void link(int x,int y){
if(find(x)==find(y)) return ;
make_root(x); fa[x]=y;
}
inline void cut(int x,int y){
make_root(x); access(y); splay(y);
if(ch[y][0]==x) y=0,fa[x]=0,up(y);
}
inline void Insert(int id){
RG int x=e[id].u,y=e[id].v;
if(x==y){ cnm[id]=m+1; return ; }
if(find(x)==find(y)){
RG int tmp=query(x,y);
cnm[id]=tmp;
cut(e[tmp].u,n+tmp);
cut(e[tmp].v,n+tmp);
}
cur(n+id,id);
link(x,n+id);
link(y,n+id);
}
inline void init(){
n=gi(),m=gi(),k=gi(),type=gi();
for(RG int i=0;i<=n;i++) cur(i,m+1);
for(RG int i=1;i<=m;i++){
e[i].u=gi(),e[i].v=gi();
Insert(i);
}
}
//------------ 主席树 --------------------------
int ans,cnt,A[N];
int sz,rt[N],sum[N*20];
int ls[N*20],rs[N*20];
inline void build(int& x,int y,int l,int r,int v){
x=++sz;
if(l==r){ sum[x]=sum[y]+1; return ; }
RG int mid=(l+r)>>1;
if(v<=A[mid]){ rs[x]=rs[y];
build(ls[x],ls[y],l,mid,v);
}
else{ ls[x]=ls[y];
build(rs[x],rs[y],mid+1,r,v);
}
sum[x]=sum[ls[x]]+sum[rs[x]];
}
inline int query(int x,int y,int l,int r,int v){
if(l==r){ return A[l]<=v?sum[x]-sum[y]:0; }
RG int mid=(l+r)>>1,ret=sum[ls[x]]-sum[ls[y]];
if(v<=A[mid]) return query(ls[x],ls[y],l,mid,v);
else return query(rs[x],rs[y],mid+1,r,v)+ret;
}
//----------------------------------------------
inline void work(){
for(RG int i=1;i<=m;i++) A[i]=cnm[i];
sort(A+1,A+m+1); A[0]=-1;
for(RG int i=1;i<=m;i++)
if(A[i]!=A[cnt]) A[++cnt]=A[i];
if(A[cnt]<m+1) A[++cnt]=m+1;
for(RG int i=1;i<=m;i++)
build(rt[i],rt[i-1],1,cnt,cnm[i]);
while(k--){
RG int l=gi(),r=gi();
if(type) l^=ans,r^=ans;
ans=n-query(rt[r],rt[l-1],1,cnt,l-1);
printf("%d\n",ans);
}
}
int main(){ init(); work(); return 0; }