D.Discovery-of-cycles
标签：LCT、尺取法
根据题意，只要求出左边界为i时，边界内所有边能构成环时最小的右边界ans[i]，即可O(1)查询答案。（若不可能构成环则ans[i]=m+1，查询答案时判断r与ans[l]的大小关系）
由于ans[i]单调递增，可以采用尺取法。若当前区间不能构成环则调整右边界（加边），否则计算当前ans[l]，并调整左边界（去边）。
判断是否构成环可以通过并查集，但一般来说并查集只支持加边不支持去边。所以需要借助LCT中的Link和Cut操作实现加边去边，并通过Findroot判断是否相连。
当然这只是LCT的一小部分功能。。
#include<bits/stdc++.h> using namespace std; const int N=2e6+5,INF=0x3f3f3f3f; struct Link_Cut_Tree{ int top,ch[N][2],ff[N],val[N],tag[N],q[N]; void init(int n) { for (int i=1;i<=n;i++) { ch[i][0]=ch[i][1]=ff[i]=tag[i]=0; } } bool isroot(int x) { return ch[ff[x]][0]!=x && ch[ff[x]][1]!=x; } void push_down(int x) { if (tag[x]) { swap(ch[x][0],ch[x][1]); tag[ch[x][0]]^=1; tag[ch[x][1]]^=1; tag[x]=0; } } void Rotate(int x) { int y=ff[x],z=ff[y],k=ch[y][1]==x; if (!isroot(y)) { ch[z][ch[z][1]==y]=x; } ff[x]=z; ch[y][k]=ch[x][k^1],ff[ch[y][k]]=y; ch[x][k^1]=y,ff[y]=x; } void Splay(int x) { top=1;q[top]=x; for (int i=x;!isroot(i);i=ff[i]) q[++top]=ff[i]; for (int i=top;i;i--) push_down(q[i]); while(!isroot(x)) { int y=ff[x],z=ff[y]; if (!isroot(y)) { if ((ch[y][0]==x)^(ch[z][0]==y)) Rotate(x); else Rotate(y); } Rotate(x); } } void Access(int x) { for (int y=0;x;y=x,x=ff[x]) { Splay(x);ch[x][1]=y; } } void Makeroot(int x) { Access(x);Splay(x); tag[x]^=1; push_down(x); } int Findroot(int x) { Access(x); Splay(x); push_down(x); while(ch[x][0]) { push_down(x);x=ch[x][0]; } Splay(x); return x; } void Split(int x,int y) { Makeroot(x); Access(y); Splay(y); } void Link(int x,int y) { Makeroot(x); if (Findroot(y)==x) return; ff[x]=y; } void Cut(int x,int y) { Makeroot(x); if (Findroot(y)!=x || ff[y]!=x || ch[y][0]) return; ff[y]=ch[x][1]=0; } bool Connect(int x,int y) { return Findroot(x)==Findroot(y); } }lct; int T,n,m,q; int ans[N],u[N],v[N]; int main() { cin>>T; while(T--) { cin>>n>>m>>q; lct.init(n); for (int i=1;i<=m;i++) { scanf("%d%d",&u[i],&v[i]); } int l=1,r=1; while(l<=m) { if (r<=m && !lct.Connect(u[r],v[r])) lct.Link(u[r],v[r]),r++; else { ans[l]=r; lct.Cut(u[l],v[l]); l++; } } int lastans=0; for (int i=1;i<=q;i++) { int l,r; scanf("%d%d",&l,&r); int k1=(l^lastans)%m+1; int k2=(r^lastans)%m+1; l=min(k1,k2);r=max(k1,k2); if (ans[l]>r) { printf("No\n"); lastans=0; } else { printf("Yes\n"); lastans=1; } } } return 0; }