[文章目录]
Description
N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。强制在线，n,m<=2*10^5
我们只需要知道[l,r]里的边有用的个数，所谓有用就是在从l开始连每条边，连到当前这条边，当前边的两端点未联通。
LCT顺次加边关于边的编号的大小维护最大生成树，统计每条边前面到哪里才能够使当前边没用，即两端点在最大生成树路径上边权的最小值。
那么每次查询就相当于查询区间[l,r]内，该值小于l的个数，主席树即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201000
int n,m,q,ty;
struct Splay
{
Splay *c[2],*fa;
int w,mi; bool tur;
Splay(int x);
void reverse(){swap(c[0],c[1]); tur^=1;}
void pushup(){mi=min(c[0]->mi,min(c[1]->mi,w));}
void pushdown();
}*null=new Splay(N),*t[N];
Splay::Splay(int x)
{
c[0]=c[1]=fa=null?null:this;
tur=0; w=mi=x;
}
void Splay::pushdown()
{
if(tur)
{
if(c[0]!=null) c[0]->reverse();
if(c[1]!=null) c[1]->reverse();
tur=0;
}
}
bool isr(Splay *x){return x!=x->fa->c[0]&&x!=x->fa->c[1];}
void rotate(Splay *x)
{
if(isr(x)) return ;
Splay *y=x->fa; int l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r]; x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(!isr(y)) y->fa->c[y==y->fa->c[1]]=x;
y->fa=x; y->pushup(); x->pushup();
}
void downall(Splay *x)
{
if(!isr(x)) downall(x->fa);
x->pushdown();
}
void splay(Splay *x)
{
downall(x); Splay *y;
while(!isr(x))
{
y=x->fa;
if(!isr(y)) rotate((x==y->c[0])^(y==y->fa->c[0])?x:y);
rotate(x);
}
}
void access(Splay *x)
{
Splay *t=null;
while(x!=null)
{
splay(x);
x->c[1]=t; x->pushup();
t=x; x=x->fa;
}
}
void moveroot(Splay *x) {access(x); splay(x); x->reverse();}
void link(Splay *x,Splay *y){moveroot(x); x->fa=y;}
void cut(Splay *x,Splay *y)
{
moveroot(x); access(y); splay(y);
y->c[0]=x->fa=null; y->pushup();
}
bool ats(Splay *x,Splay *y)
{
while(x->fa!=null) x=x->fa;
while(y->fa!=null) y=y->fa;
return x==y;
}
Splay *find(Splay *x)
{
if(x->w<=x->c[0]->mi&&x->w<=x->c[1]->mi) return x;
if(x->c[0]->mi<x->c[1]->mi) return find(x->c[0]);
else return find(x->c[1]);
}
struct seg
{
int ls,rs,s;
}s[N*40];
int se,rt[N];
void insert(int &r1,int r2,int l,int r,int x,int y)
{
r1=++se; s[r1].s=s[r2].s+y;
if(l==r) return ; int mid=(l+r)>>1;
if(x<=mid) s[r1].rs=s[r2].rs,insert(s[r1].ls,s[r2].ls,l,mid,x,y);
else s[r1].ls=s[r2].ls,insert(s[r1].rs,s[r2].rs,mid+1,r,x,y);
}
int query(int p,int l,int r,int x)
{
if(!p) return 0;
if(x>=r) return s[p].s; int mid=(l+r)>>1;
if(x<=mid) return query(s[p].ls,l,mid,x);
else return s[s[p].ls].s+query(s[p].rs,mid+1,r,x);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&q,&ty);
int i;
for(i=1;i<=n;++i) t[i]=new Splay(N);
insert(rt[0],rt[0],0,m,0,n-1);
Splay *p; int x,y;
for(i=1;i<=m;++i)
{
rt[i]=rt[i-1]; scanf("%d%d",&x,&y);
if(x==y) continue;
if(!ats(t[x],t[y])) insert(rt[i],rt[i],0,m,0,-1);
else
{
moveroot(t[x]); access(t[y]); splay(t[y]);
insert(rt[i],rt[i],0,m,t[y]->mi,-1);
splay(p=find(t[y])); p->pushdown();
p->c[0]->fa=null; p->c[1]->fa=null;
free(p);
}
p=new Splay(i);
link(t[x],p);
link(t[y],p);
insert(rt[i],rt[i],0,m,i,1);
}
int l,r,ans=0;
while(q--)
{
scanf("%d%d",&l,&r);
if(ty) l^=ans,r^=ans;
ans=query(rt[r],0,m,l-1)+1;
printf("%d\n",ans);
}
return 0;
}
/* 3 5 4 0 1 3 1 2 2 1 3 2 2 2 2 3 1 5 5 5 1 2*/