题目描述：

　　N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。

输入格式：

　　第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。 接下来M行，代表图中的每条边。 接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

输出格式：

　　K行每行一个整数代表该组询问的联通块个数。

题解：

　　连通问题首先考虑LCT。

　　考虑连通块个数的计算方法。

　　连通块个数=点数-去掉重边后的边数。

　　逐个枚举边，如果这条边连接的两个点没有连通，连接这条边；反之，把两点间最早的边弹出，连接这条边，并记录弹出边的编号。

　　每次查询区间时，如果这条边弹出的边在区间内，那么这条边是无效的。

　　所以问题转化为求区间内小于某个数的数的个数，可以主席树维护。

　　时间复杂度$O(nlog_n)$

Code:

#include
#include
using namespace std;
const int N=;
const int inf=1e9+;
int n,m,k,ty,cnt,top;
int a[N<<],st[N<<],ch[N<<][],f[N<<],rev[N<<],mi[N<<]; int u[N],v[N],rt[N],b[N],an[N]; struct seg{ int lc,rc,w; }t[N<<]; int read() { int s=;char c=getchar(); while(c<''||c>'') c=getchar();
while(c>=''&&c<=''){ s=(s<<)+(s<<)+c-''; c=getchar(); } return s; } int get(int x) { return ch[f[x]][]==x; } bool isroot(int x) { return ch[f[x]][]!=x&&ch[f[x]][]!=x; } void pushup(int x) { mi[x]=a[x]; if(ch[x][]) mi[x]=min(mi[x],mi[ch[x][]]); if(ch[x][]) mi[x]=min(mi[x],mi[ch[x][]]); } void pushdown(int x) { if(rev[x]){ swap(ch[x][],ch[x][]); if(ch[x][]) rev[ch[x][]]^=; if(ch[x][]) rev[ch[x][]]^=; rev[x]=; } } void rotate(int x) { int y=f[x],z=f[y],k=get(x); if(!isroot(y)){ if(ch[z][]==y) ch[z][]=x; else ch[z][]=x; } f[x]=z;f[y]=x;f[ch[x][k^]]=y; ch[y][k]=ch[x][k^];ch[x][k^]=y; pushup(y);pushup(x); } void splay(int x) { top=;st[++top]=x; for(int i=x;!isroot(i);i=f[i]) st[++top]=f[i]; for(int i=top;i>=;i--) pushdown(st[i]);
while(!isroot(x)){
int y=f[x];
if(!isroot(y)){
if(get(x)==get(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
}
void access(int x)
{
for(int y=;x;y=x,x=f[x]){
splay(x);ch[x][]=y;pushup(x);
}
}
void makeroot(int x)
{
access(x);splay(x);
rev[x]^=;
}
void split(int x,int y)
{
makeroot(x);
access(y);splay(y);
}
void link(int x,int y)
{
makeroot(x);
f[x]=y;
}
void cut(int x,int y)
{
split(x,y);
f[x]=ch[y][]=;
}
int find(int x)
{
access(x);splay(x);
pushdown(x);
while(ch[x][]){
pushdown(ch[x][]);
x=ch[x][];
}
splay(x);
return x;
}
void insert(int lk,int &rk,int l,int r,int x)
{
if(rk==) rk=++cnt;
t[rk].w=t[lk].w+;
if(l==r) return;
int mid=(l+r)>>;
if(x<=mid){ t[rk].rc=t[lk].rc; insert(t[lk].lc,t[rk].lc,l,mid,x); } else{ t[rk].lc=t[lk].lc; insert(t[lk].rc,t[rk].rc,mid+,r,x); } } int que(int lk,int rk,int L,int R,int l,int r) { if(L>=l&&R<=r) return t[rk].w-t[lk].w; int mid=(L+R)>>;
if(r<=mid) return que(t[lk].lc,t[rk].lc,L,mid,l,r); else if(l>mid) return que(t[lk].rc,t[rk].rc,mid+,R,l,r);
else return que(t[lk].lc,t[rk].lc,L,mid,l,r)+que(t[lk].rc,t[rk].rc,mid+,R,l,r);
}
int main()
{
n=read();m=read();k=read();ty=read();
for(int i=;i<=n;i++) a[i]=inf;
for(int i=;i<=m;i++){
u[i]=read();v[i]=read();a[i+n]=i;
if(u[i]!=v[i]){
int x=find(u[i]),y=find(v[i]);
if(x==y){
split(u[i],v[i]);
b[i]=mi[v[i]];
cut(u[b[i]],b[i]+n);
cut(b[i]+n,v[b[i]]);
}
link(u[i],i+n);
link(i+n,v[i]);
insert(rt[i-],rt[i],,m,b[i]);
}
else rt[i]=rt[i-];
}
for(int i=;i<=k;i++){
int l=read(),r=read();
if(ty){
l^=an[i-];r^=an[i-];
}
an[i]=n-que(rt[l-],rt[r],,m,,l-);
}
for(int i=;i<=k;i++) printf("%d\n",an[i]);
return ;
}