题目大意：给定n个点m条边无向图，每次询问求当图中有编号为[L,R]的边时，整个图的联通块个数，强制在线
神题！(发现好久以前的题解没有写完诶)
我们要求图中联通块的个数，似乎不可搞啊。
联通块个数=n-树边条数！
考虑每条边的贡献，我们按编号从小到大暴力枚举每一条边。
考虑用$LCT$维护森林。
设新加入的这条边编号为$e$，连接了$x,y$两个点
如果$x,y$原来不连通，说明加入$e$会让图中多一条树边。边e对$L\in [1,e],R\geq e$的图$[L,R]$产生一点贡献
如果$x,y$原来就联通，说明加入$e$会产生环，并不会影响联通块个数。我们找出$e$所在环里编号最小的边$x$
当$L\leq x$时，删掉边$x$，图$[L,R]$的树边个数不变。
当$L>x$时，删掉边$x$，会让图$[L,R]$少一条树边。那么边$x$会对$L\in[x+1,e],R\geq e$的的图$[L,R]$产生一点贡献
如何处理询问？我们可以用主席树，主席树不同的根作为右端点，线段树维护对左端点的贡献。每次查询，主席树相减，然后单点查询
如何维护贡献？主席树上打差分实现区间修改
如何维护编号最小的边？把边转化成点扔到$LCT$里就行啦
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 401000
#define M1 201000
#define S1 (N1<<1)
#define T1 (N1<<2)
#define ll long long
#define uint unsigned int
#define rint register int
#define ull unsigned long long
#define dd double
#define il inline
#define inf 1000000000
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,T,type;
struct Edge{
int x[M1],y[M1],cte;
void ae(int u,int v)
{cte++;x[cte]=u,y[cte]=v;}
}E;
struct SEG{
int ls[N1*],rs[N1*],sum[N1*],root[N1],tot;
void pushup(int rt){sum[rt]=sum[ls[rt]]+sum[rs[rt]];}
void build(int l,int r,int &rt)
{
int mid=(l+r)>>; rt=++tot;
if(l==r) return;
build(l,mid,ls[rt]);
build(mid+,r,rs[rt]);
}
void update(int x,int l,int r,int r1,int &r2,int w)
{
if((!r2)||(r1==r2)){r2=++tot,sum[r2]=sum[r1],ls[r2]=ls[r1],rs[r2]=rs[r1];}
if(l==r) {sum[r2]+=w; return;} int mid=(l+r)>>;
if(x<=mid) update(x,l,mid,ls[r1],ls[r2],w);
else update(x,mid+,r,rs[r1],rs[r2],w);
pushup(r2);
}
int query(int L,int R,int l,int r,int rt)
{
if(!rt||L>R) return ;
if(L<=l&&r<=R) return sum[rt];
int mid=(l+r)>>,ans=;
if(L<=mid) ans+=query(L,R,l,mid,ls[rt]);
if(R>mid) ans+=query(L,R,mid+,r,rs[rt]);
return ans;
}
}s;
namespace lct{
int ch[N1][],fa[N1],mi[N1],id[N1],rev[N1],tot;
int idf(int x){return ch[fa[x]][]==x?:;}
int isroot(int x){return (ch[fa[x]][]==x||ch[fa[x]][]==x)?:;}
void pushup(int x){mi[x]=min(x,min(mi[ch[x][]],mi[ch[x][]]));}
void revers(int x){swap(ch[x][],ch[x][]),rev[x]^=;}
void pushdown(int x){if(rev[x]){revers(ch[x][]),revers(ch[x][]),rev[x]^=;}}
void rot(int x)
{
int y=fa[x],ff=fa[y],px=idf(x),py=idf(y);
if(!isroot(y)) ch[ff][py]=x; fa[x]=ff;
fa[ch[x][px^]]=y,ch[y][px]=ch[x][px^];
ch[x][px^]=y,fa[y]=x;
pushup(y),pushup(x);
}
int stk[N1],tp;
void splay(int x)
{
int y=x; stk[++tp]=x;
while(!isroot(y)){stk[++tp]=fa[y],y=fa[y];}
while(tp){pushdown(stk[tp--]);}
while(!isroot(x))
{
y=fa[x];
if(isroot(y)) rot(x);
else if(idf(y)==idf(x)) rot(y),rot(x);
else rot(x),rot(x);
}
}
void access(int x){for(int y=;x;y=x,x=fa[x]) splay(x),ch[x][]=y,pushup(x);}
void mkroot(int x){access(x),splay(x),revers(x);}
void split(int x,int y){mkroot(x),access(y),splay(y);}
int fdroot(int x){access(x),splay(x);while(ch[x][])pushdown(ch[x][]),x=ch[x][];return x;}
void cut(int x,int y){split(x,y);fa[x]=ch[y][]=,pushup(y);}
void link(int x,int y){split(x,y);fa[x]=y;}
//int isconn(int x,int y){split(x,y);if(!ch[x][1]&&fa[x]=y&&ch[y][0]==x) return 1;}
void solve(int x,int y,int e)
{
split(x+m,y+m);
if(x==y){
int r1=s.root[e-],r2=s.root[e]=++s.tot;
s.sum[r2]=s.sum[r1],s.ls[r2]=s.ls[r1],s.rs[r2]=s.rs[r1];
}else if(fdroot(y+m)!=x+m){
s.update(,,m,s.root[e-],s.root[e],);
if(e<m) s.update(e+,,m,s.root[e-],s.root[e],-);
}else{
int id=mi[y+m],xx=E.x[id],yy=E.y[id];
cut(id,xx+m); cut(id,yy+m);
s.update(id+,,m,s.root[e-],s.root[e],);
if(e<m) s.update(e+,,m,s.root[e-],s.root[e],-);
}
link(e,x+m),link(e,y+m);
}
};
int tot; int main()
{
int i,j,x,y,Q,sx,sy,ans=; tot=n+m;
scanf("%d%d%d%d",&n,&m,&Q,&type);
for(j=;j<=m;j++) x=gint(), y=gint(), E.ae(x,y);
s.build(,m,s.root[]);
for(lct::mi[]=inf,i=;i<=n+m;i++) lct::mi[i]=i;
for(j=;j<=m;j++)
{
x=E.x[j]; y=E.y[j];
lct::solve(x,y,j);
}
for(j=;j<=Q;j++)
{
x=gint(), y=gint();
if(type) x^=ans,y^=ans;
sx=s.query(,x,,m,s.root[x-]);
sy=s.query(,x,,m,s.root[y]);
ans=n-(sy-sx);
printf("%d\n",ans);
}
return ;
}