题解：
还是比较简单的
首先我们的思路是 确定起点 然后之后贪心的选择边（也就是越靠前越希望选）
我们发现我们只需要将起点从后向前枚举
然后用lct维护连通性
因为强制在线，所以用主席树记录状态就可以了
*数组开小查了很久
代码：
#include <bits/stdc++.h> using namespace std; #define IL inline #define rint register int #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) const int INF=1e9; const int N=4e5+10; char ss[1<<24],*A=ss,*B=ss; IL char gc() { return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++; } template<class T> void read(T &x) { rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=c^48; while (c=gc(),47<c&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f; } int data[N],ls[N],rs[N],fa[N],v[N]; bool rev[N]; IL void updata(int x) { data[x]=min(min(data[ls[x]],data[rs[x]]),v[x]); } IL void down(int x) { if (!rev[x]) return; rev[ls[x]]^=1; rev[rs[x]]^=1; swap(ls[x],rs[x]); rev[x]=0; } IL bool pd(int x) { int fa1=fa[x]; if (ls[fa1]!=x&&rs[fa1]!=x) return(0); else return(1); } void rotate(int x,int y) { int fa1=fa[x]; if (y==1) { rs[fa1]=ls[x]; if (ls[x]) fa[ls[x]]=fa1; } else { ls[fa1]=rs[x]; if (rs[x]) fa[rs[x]]=fa1; } fa[x]=fa[fa1]; if (pd(fa1)) { if (ls[fa[fa1]]==fa1) ls[fa[fa1]]=x; else rs[fa[fa1]]=x; } fa[fa1]=x; if (y==1) ls[x]=fa1; else rs[x]=fa1; updata(fa1); updata(x); } void dfs(int x) { if (pd(x)) dfs(fa[x]); down(x); } void splay(int x) { dfs(x); int fa1=fa[x]; while (pd(x)) { if (!pd(fa1)) { if (x==ls[fa1]) rotate(x,2); else rotate(x,1); } else if (ls[fa[fa1]]==fa1) if (ls[fa1]==x) rotate(fa1,2),rotate(x,2); else rotate(x,1),rotate(x,2); else if (rs[fa1]==x) rotate(fa1,1),rotate(x,1); else rotate(x,2),rotate(x,1); fa1=fa[x]; } } void access(int x) { for (int y=0;x;y=x,x=fa[x]) { splay(x); rs[x]=y; updata(x); } } int fdr(int x) { access(x); splay(x); while (ls[x]) x=ls[x]; return(x); } void mkr(int x) { access(x); splay(x); rev[x]^=1; } void split(int x,int y) { mkr(x); access(y); splay(y); } void link(int x,int y) { mkr(x); access(y); splay(y); fa[x]=y; } void cut(int x,int y) { mkr(x); access(y); splay(y); ls[y]=fa[x]=0; updata(y); } #define mid ((h+t)/2) int root[N],jl1[N],jl2[N]; struct segtment{ int p[N*20],ls[N*20],rs[N*20],cnt; segtment() { cnt=0; } void updata(int x) { p[x]=p[ls[x]]+p[rs[x]]; } void change(int last,int &x,int h,int t,int pos,int k) { x=++cnt; ls[x]=ls[last]; rs[x]=rs[last]; p[x]=p[last]+k; if (h==t) return; if (pos<=mid) change(ls[last],ls[x],h,mid,pos,k); else change(rs[last],rs[x],mid+1,t,pos,k); updata(x); } int query(int x,int h,int t,int h1,int t1) { if (h1<=h&&t<=t1) return(p[x]); int ans=0; if (h1<=mid) ans+=query(ls[x],h,mid,h1,t1); if (mid<t1) ans+=query(rs[x],mid+1,t,h1,t1); return(ans); } }S; int n,m,k,type; int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); read(n); read(m); read(k); read(type); int ans=0; data[0]=v[0]=INF; rep(i,1,n) v[i]=INF,v[i+n]=i; rep(i,1,m)v[i+n]=i; int p=0,maxn=0; rep(i,1,m) { // cout<<i<<endl; int x,y; root[i]=root[i-1]; read(x); read(y); if (x==y) continue; jl1[i]=x;jl2[i]=y; mkr(y); if (fdr(x)==y) { split(x,y); int x1=data[y]; cut(x1+n,jl1[x1]); cut(x1+n,jl2[x1]); S.change(root[i],root[i],1,m,x1,-1); p--; } p++; link(i+n,x); link(i+n,y); S.change(root[i],root[i],1,m,i,1); if (p>n) return 0; maxn=max(maxn,p); } rep(i,1,k) { int x,y; read(x); read(y); if (type) x^=ans,y^=ans; printf("%d ",ans=n-S.query(root[y],1,m,x,y)); } return 0; }