给定 \(n\) 个点 \(m\) 条边的无向图，每次询问保留图中编号在 \([l,r]\) 的边的时候图中联通块个数。强制在线。
\(n,m\leq 2\cdot 10^5\)
Solution先考虑一下假如可以离线的话怎么做。
把询问按照右端点排序，维护边权 最大生成树，这里的"边权"指的是边的标号。
每次尝试加边，如果这条边连接的两条边不连通就直接加，否则从环上找一条边权最小的边替换，然后用线段树维护当前用了哪条边，如果要加入就对应位置 \(+1\)，要删除就对应位置 \(-1\) 。维护生成树的过程用 \(LCT\) 实现。这样对于询问 \([l,r]\) 就查一下在线段树上 \([l,r]\) 的权值和 \(sum\) 表示当前在图上用到了 \(sum\) 条边，\(n-sum\) 即为答案。
然后考虑在线做法。
把线段树换成主席树就好了。
大概扫了一下网上的题解好像做法都是搞出来一个 \(ntr[i]\) 表示加入第 \(i\) 条边的时候替换掉了哪条边，如果没有替换掉边则值为 \(0\)。然后每次询问的时候找主席树 \([0,l-1]\) 的 \(sum\) 就好了。。。然而我并不能想明白为什么是这样，只能用我那种有加有减的做法了...
Code #include<bits/stdc++.h> using std::min; using std::max; using std::swap; using std::vector; typedef double db; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B) const int N=4e5+5; #define ls ch[x][0] #define rs ch[x][1] int ch[N][2],fa[N],mn[N],stk[N],father[N]; int n,m,k,type,val[N],idx[N],rev[N],top,rt[N]; struct Edge{ int x,y; }edge[N]; void pushup(int x){ mn[x]=min(mn[ls],min(mn[rs],val[x])); } void pushr(int x){ swap(ls,rs);rev[x]^=1; } void pushdown(int x){ if(rev[x]) pushr(ls),pushr(rs),rev[x]=0; } bool nroot(int x){ return ch[fa[x]][0]==x or ch[fa[x]][1]==x; } int find(int x){ return father[x]==x?x:father[x]=find(father[x]); } void rotate(int x){ int y=fa[x],z=fa[y],d=ch[y][1]==x,dd=ch[z][1]==y; ch[y][d]=ch[x][d^1];if(ch[x][d^1]) fa[ch[x][d^1]]=y; fa[x]=z;if(nroot(y)) ch[z][dd]=x; ch[x][d^1]=y;fa[y]=x;pushup(y); } void splay(int x){ int now=x;stk[++top]=now; while(nroot(now)) now=fa[now],stk[++top]=now; while(top) pushdown(stk[top--]); while(nroot(x)){ int y=fa[x],z=fa[y]; if(nroot(y)) rotate((ch[y][1]==x)^(ch[z][1]==y)?x:y); rotate(x); } pushup(x); } void access(int x){ for(int y=0;x;y=x,x=fa[x]) splay(x),rs=y;pushup(x); } void makeroot(int x){ access(x),splay(x),pushr(x); } void link(int x,int y){ makeroot(x);fa[x]=y; } void cut(int x,int y){ makeroot(x),access(y),splay(y); fa[x]=ch[y][0]=0;pushup(y); } void split(int x,int y){ makeroot(x),access(y),splay(y); } int getint(){ int X=0,w=0;char ch=getchar(); while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } namespace hjt{ int tot,ch[N*40][2],sum[N*40]; void update(int &x,int las,int l,int r,int ql,int qr,int c){ x=++tot; sum[x]=sum[las]+c;ls=ch[las][0];rs=ch[las][1]; if(l==r) return; int mid=l+r>>1; ql<=mid?update(ls,ch[las][0],l,mid,ql,qr,c):update(rs,ch[las][1],mid+1,r,ql,qr,c); } int query(int las,int x,int l,int r,int ql,int qr){ if(ql<=l and r<=qr) return sum[x]-sum[las]; int mid=l+r>>1,ans=0; if(ql<=mid) ans+=query(ch[las][0],ls,l,mid,ql,qr); if(mid<qr) ans+=query(ch[las][1],rs,mid+1,r,ql,qr); return ans; } }; signed main(){ mn[0]=1e9; n=getint(),m=getint(),k=getint(),type=getint(); for(int i=1;i<=m;i++){ int x=getint(),y=getint(); edge[i]=(Edge){x,y};val[i+n]=i; } for(int i=0;i<=n;i++) father[i]=i,val[i]=1e9; for(int i=1;i<=m;i++){ rt[i]=rt[i-1]; int r1=find(edge[i].x),r2=find(edge[i].y); if(r1!=r2){ hjt::update(rt[i],rt[i],0,m,i,i,1); father[r1]=r2; } else{ if(edge[i].x==edge[i].y) continue; split(edge[i].x,edge[i].y); int xx=mn[edge[i].y]; hjt::update(rt[i],rt[i],0,m,xx,xx,-1); hjt::update(rt[i],rt[i],0,m,i,i,1); cut(edge[xx].x,xx+n),cut(edge[xx].y,xx+n); } link(edge[i].x,i+n),link(edge[i].y,i+n); } int lasans=0; while(k--){ int l=getint(),r=getint(); if(type) l^=lasans,r^=lasans; int p=hjt::query(rt[l-1],rt[r],0,m,l,r); printf("%d\n",lasans=n-p); } return 0; }