欢迎访问~原文出处——
题意概括
N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。
N,M,Q<=200000
题解
这题hzwer还是写的很好的……
代码
#include#include #include #include #include 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