Description
N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。
Input
第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。
接下来M行，代表图中的每条边。
接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。
Output
K行每行一个整数代表该组询问的联通块个数。
Sample Input
3 5 4 0
1 3
1 2
2 1
3 2
2 2
2 3
1 5
5 5
1 2
1 3
1 2
2 1
3 2
2 2
2 3
1 5
5 5
1 2
Sample Output
2
1
3
1
1
3
1
HINT
对于100%的数据，1≤N、M、K≤200,000。
Solution
$namespace$真是个好东西QAQ
每次往里加边，如果构成环的话就把最早的那条边删掉，这个可以用$LCT$随便做。
定义一个数组$Early[i]$，表示加第$i$条边的时候，会把哪条边删掉。
特殊的，如果不删边，$Early[i]=0$。如果第$i$条边是自环，$Early[i]=i$。
然后对$Early$数组建主席树，每次询问的答案就是$[l,r]$区间内小于等于$l-1$的数个个数。
正确性……如果一条边$i$的$Early[i]$在$l$后面的话，那么加入$i$的时候，因为会产生环所以不会对连通块情况产生影响。否则如果$Early[i]$在$l$的前面的话，加入$i$就会对连通块情况产生影响……
大体就是这样子具体我也不会
Code
#include<iostream>
#include<cstdio>
#define N (400009)
using namespace std; int n,m,k,opt,Early[N],x[N],y[N]; namespace LCT
{
int Father[N],Son[N][],Val[N],Min[N],Rev[N]; int Get(int x)
{
return Son[Father[x]][]==x;
}
int Is_root(int x)
{
return Son[Father[x]][]!=x && Son[Father[x]][]!=x;
}
void Pushup(int x)
{
Min[x]=x;
int ls=Son[x][],rs=Son[x][];
if (Val[Min[ls]]<Val[Min[x]]) Min[x]=Min[ls];
if (Val[Min[rs]]<Val[Min[x]]) Min[x]=Min[rs];
}
void Pushdown(int x)
{
if (Rev[x])
{
Rev[Son[x][]]^=;
Rev[Son[x][]]^=;
swap(Son[x][],Son[x][]);
Rev[x]=;
}
}
void Rotate(int x)
{
int wh=Get(x);
int fa=Father[x],fafa=Father[fa];
if (!Is_root(fa)) Son[fafa][Son[fafa][]==fa]=x;
Father[fa]=x; Son[fa][wh]=Son[x][wh^];
if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
Father[x]=fafa; Son[x][wh^]=fa;
Pushup(fa); Pushup(x);
}
void Push(int x)
{
if (!Is_root(x)) Push(Father[x]);
Pushdown(x);
}
void Splay(int x)
{
Push(x);
for (int fa; !Is_root(x); Rotate(x))
if (!Is_root(fa=Father[x]))
Rotate(Get(fa)==Get(x)?fa:x);
}
void Access(int x)
{
for (int y=; x; y=x,x=Father[x])
Splay(x), Son[x][]=y, Pushup(x);
}
void Make_root(int x)
{
Access(x); Splay(x); Rev[x]^=;
}
int Find_root(int x)
{
Access(x); Splay(x);
while (Son[x][]) x=Son[x][];
return x;
}
void Link(int x,int y)
{
Make_root(x); Father[x]=y;
}
void Cut(int x,int y)
{
Make_root(x); Access(y); Splay(y);
Son[y][]=Father[x]=; Pushup(y);
}
int Query(int x,int y)
{
Make_root(x); Access(y); Splay(y);
return Min[y];
}
void Build_Early()
{
for (int i=; i<=m; ++i) Val[n+i]=i;
for (int i=; i<=n; ++i) Val[i]=2e8,Min[i]=i;
for (int i=; i<=m; ++i)
{
scanf("%d%d",&x[i],&y[i]);
if (x[i]==y[i]) {Early[i]=i; continue;}
if (Find_root(x[i])!=Find_root(y[i]))
Link(x[i],i+n), Link(y[i],i+n);
else
{
int p=Query(x[i],y[i]);
Early[i]=p-n;
Cut(x[p-n],p); Cut(y[p-n],p);
Link(x[i],i+n); Link(y[i],i+n);
}
}
}
} namespace Sgt
{
struct Sgt{int ls,rs,val;}Segt[N*];
int sgt_num,Root[N]; int Update(int pre,int l,int r,int x)
{
int now=++sgt_num;
Segt[now]=Segt[pre];
Segt[now].val++;
if (l==r) return now;
int mid=(l+r)>>;
if (x<=mid) Segt[now].ls=Update(Segt[now].ls,l,mid,x);
else Segt[now].rs=Update(Segt[now].rs,mid+,r,x);
return now;
}
int Query(int u,int v,int l,int r,int l1,int r1)
{
if (l>r1 || r<l1) return ;
if (l1<=l && r<=r1) return Segt[v].val-Segt[u].val;
int mid=(l+r)>>;
return Query(Segt[u].ls,Segt[v].ls,l,mid,l1,r1)+Query(Segt[u].rs,Segt[v].rs,mid+,r,l1,r1);
}
void Solve()
{
for (int i=; i<=m; ++i)
Root[i]=Update(Root[i-],,2e5,Early[i]);
int ans=,l,r;
for (int i=; i<=k; ++i)
{
scanf("%d%d",&l,&r);
if (opt) l^=ans, r^=ans;
ans=n-Query(Root[l-],Root[r],,2e5,,l-);
printf("%d\n",ans);
}
}
} int main()
{
scanf("%d%d%d%d",&n,&m,&k,&opt);
LCT::Build_Early();
Sgt::Solve();
}