欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ3514
题意概括
N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。
N,M,Q<=200000
题解
这题hzwer还是写的很好的……
代码
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=200005,S=N*2,Inf=23333333;
int n,m,k,type,prev_e[N];
struct Edge{
int x,y;
}e[N];
int fa[S],son[S][2],rev[S],val[S],Min[S];
void clear(int x,int v){
fa[x]=son[x][0]=son[x][1]=rev[x]=0;
val[x]=Min[x]=v;
}
bool isroot(int x){
return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
void pushup(int x){
Min[x]=min(val[x],min(Min[son[x][0]],Min[son[x][1]]));
}
void pushdown(int x){
if (rev[x]){
rev[x]=0;
rev[son[x][0]]^=1;
rev[son[x][1]]^=1;
swap(son[x][0],son[x][1]);
}
}
void pushadd(int x){
if (!isroot(x))
pushadd(fa[x]);
pushdown(x);
}
int wson(int x){
return son[fa[x]][1]==x;
}
void rotate(int x){
if (isroot(x))
return;
int y=fa[x],z=fa[y],L=wson(x),R=L^1;
if (!isroot(y))
son[z][wson(y)]=x;
fa[x]=z,fa[y]=x,fa[son[x][R]]=y;
son[y][L]=son[x][R],son[x][R]=y;
pushup(y),pushup(x);
}
void splay(int x){
pushadd(x);
for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])
if (!isroot(y))
rotate(wson(x)==wson(y)?y:x);
}
void access(int x){
int t=0;
while (x){
splay(x);
son[x][1]=t;
pushup(x);
t=x;
x=fa[x];
}
}
int find(int x){
access(x);
splay(x);
while (son[x][0])
x=son[x][0];
return x;
}
void rever(int x){
access(x);
splay(x);
rev[x]^=1;
}
void link(int x,int y){
rever(x);
fa[x]=y;
}
void split(int x,int y){
rever(x);
access(y);
splay(y);
}
void cut(int x,int y){
split(x,y);
fa[x]=son[y][0]=0;
}
const int T=5200005;
int ls[T],rs[T],sum[T],root[N],total;
void Tpushup(int rt){
sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
void build(int &rt,int L,int R){
rt=++total;
if (L==R){
ls[T]=rs[T]=sum[T]=0;
return;
}
int mid=(L+R)>>1;
build(ls[rt],L,mid);
build(rs[rt],mid+1,R);
Tpushup(rt);
}
void add(int prt,int &rt,int L,int R,int pos){
rt=++total;
if (L==R){
sum[rt]=sum[prt]+1;
return;
}
int mid=(L+R)>>1;
if (pos<=mid)
add(ls[prt],ls[rt],L,mid,pos),rs[rt]=rs[prt];
else
add(rs[prt],rs[rt],mid+1,R,pos),ls[rt]=ls[prt];
Tpushup(rt);
}
int query(int rt,int L,int R,int pos){
if (R<=pos)
return sum[rt];
if (L>pos)
return 0;
int mid=(L+R)>>1;
return query(ls[rt],L,mid,pos)+query(rs[rt],mid+1,R,pos);
}
int main(){
scanf("%d%d%d%d",&n,&m,&k,&type);
for (int i=1;i<=m;i++)
scanf("%d%d",&e[i].x,&e[i].y);
int s=n+m;
for (int i=0;i<S;i++)
clear(i,Inf);
for (int i=1;i<=m;i++){
int x=e[i].x,y=e[i].y;
if (x==y){
prev_e[i]=i;
continue;
}
if (find(x)==find(y)){
split(y,x);
int ce=prev_e[i]=Min[x];
cut(e[ce].x,ce+n);
cut(e[ce].y,ce+n);
}
else
prev_e[i]=0;
clear(i+n,i);
link(x,i+n);
link(y,i+n);
}
total=n-1;
build(root[0],0,m);
for (int i=1;i<=m;i++)
add(root[i-1],root[i],0,m,prev_e[i]);
int lastans=0;
for (int i=1;i<=k;i++){
int L,R;
scanf("%d%d",&L,&R);
if (type)
L^=lastans,R^=lastans;
int res=query(root[R],0,m,L-1)-query(root[L-1],0,m,L-1);
res=n-res;
printf("%d\n",lastans=res);
}
return 0;
}