传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3514
思路：这题思路很巧妙
首先每个连通块只要保留一棵生成树的边就可以保证连通了
把每条边的编号当做边权
我们把每条边按顺序加入，维护一个每个连通块的最大生成树
每次替换树上路径的最小边
把它替换的边的编号记录到一个数组a[i]中，如果连通了两个连通块，a[i]=0
这个显然是可以用LCT解决的
得到a[i]后，对于每个询问[l,r]，统计区间[l,r]中有多少个数小于l，用n去减即可得答案
因为我们维护的是最大生成树，如果[l,r]中有一条边x替换的边y是小于l的，那么没有编号大于等于的l边使这个连通块连通，就说明该边使两个连通块连通了，连通块数量-1
这个用可持久化线段树搞一搞即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ls ch[x][0]
#define rs ch[x][1]
const int maxn=400010,inf=1e9,maxt=10000010;
using namespace std;
struct Edge{int u,v;}E[maxn];
int n,m,k,type,Q,a[maxn],lastans;char ch;
void read(int &x){
for (ch=getchar();!isdigit(ch);ch=getchar());
for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
namespace Tseg{
int lc[maxt],rc[maxt],sum[maxt],root[maxn],tot;
void insert(int pre,int &p,int l,int r,int x){
p=++tot,sum[p]=sum[pre]+1;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) rc[p]=rc[pre],insert(lc[pre],lc[p],l,mid,x);
else lc[p]=lc[pre],insert(rc[pre],rc[p],mid+1,r,x);
}
int query(int pre,int p,int l,int r,int a,int b){
if (l==a&&r==b) return sum[p]-sum[pre];
int mid=(l+r)>>1;
if (b<=mid) return query(lc[pre],lc[p],l,mid,a,b);
else if (a>mid) return query(rc[pre],rc[p],mid+1,r,a,b);
else return query(lc[pre],lc[p],l,mid,a,mid)+query(rc[pre],rc[p],mid+1,r,mid+1,b);
}
void work(){
for (int i=1,l,r;i<=Q;i++){
read(l),read(r);
if (type) l^=lastans,r^=lastans;
printf("%d
",lastans=(n-query(root[l-1],root[r],0,m,0,l-1)));
}
}
}
struct Tlct{
int fa[maxn],ch[maxn][2],mins[maxn],val[maxn],tot;bool rev[maxn];
int which(int x){return ch[fa[x]][1]==x;}
bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void update(int x){
mins[x]=x;
if (val[mins[ls]]<val[mins[x]]) mins[x]=mins[ls];
if (val[mins[rs]]<val[mins[x]]) mins[x]=mins[rs];
}
void flip(int x){swap(ls,rs),rev[x]^=1;}
void down(int x){if (rev[x]) flip(ls),flip(rs),rev[x]^=1;}
void relax(int x){if (fa[x]) relax(fa[x]);down(x);}
void rotate(int x){
int y=fa[x],z=fa[y],nx=which(x),ny=which(y);
fa[ch[x][!nx]]=y,ch[y][nx]=ch[x][!nx];
fa[x]=z;if (!isroot(y)) ch[z][ny]=x;
fa[y]=x,ch[x][!nx]=y;update(y);
}
void splay(int x){
relax(x);
while (!isroot(x)){
int y=fa[x];
if (isroot(y)) rotate(x);
else if (which(x)==which(y)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
update(x);
}
void access(int x){for (int p=0;x;p=x,x=fa[x]) splay(x),fa[rs=p]=x,update(x);}
void makeroot(int x){access(x),splay(x),flip(x);}
void link(int x,int y){makeroot(x),fa[x]=y;}
void cut(int x,int y){makeroot(x),access(y),splay(y),ch[y][0]=fa[x]=0;}
int findrt(int x){access(x),splay(x);for (;ls;x=ls);return x;}
int query(int x,int y){makeroot(x),access(y),splay(y);return mins[y];}
void prework(){
tot=n;
for (int i=1;i<=m;i++){
int u=E[i].u,v=E[i].v;
if (u==v){a[i]=i;continue;}
if (findrt(u)==findrt(v)){
int t=query(u,v),x=val[t];
a[i]=x,cut(E[x].u,t),cut(E[x].v,t);
}
++tot,mins[tot]=tot,val[tot]=i,link(u,tot),link(v,tot);
}
for (int i=1;i<=m;i++) Tseg::insert(Tseg::root[i-1],Tseg::root[i],0,m,a[i]);
}
}lct;
int main(){
scanf("%d%d%d%d",&n,&m,&Q,&type);
lct.val[0]=inf;
for (int i=1;i<=n;i++) lct.mins[i]=i,lct.val[i]=inf;
for (int i=1;i<=m;i++) read(E[i].u),read(E[i].v);
lct.prework(),Tseg::work();
return 0;
}