Discovery of Cycles（动态树 LCT ST表）

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=886

题意：

一张无向图,q个强制在线询问,如果只用区间[l,r]的边,能否组成一个简单环

解析：

求出每个i,至少要扩展到ans[i]才能使[i,ans[i]]组成简单环,ans[i]是单调的。

所以我们可以用尺取法来维护出ans[i]，往右延时的时候加边。如果当前边两点已经在一棵树上说明可以形成环。

缩短的时候需要删除边，所以使用动态树。

最后区间求一个最小值判断是否小于等于R即可。（ST表）

代码：

/*
 *  Author : Jk_Chen
 *    Date : 2020-08-13-13.26.36
 */
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define LD long double
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair<int, int>
#define fi first
#define se second
void test() {
    cerr<<"\n";
}
template<typename T,typename... Args>void test(T x,Args... args) {
    cerr<<"> "<<x<<" ";
    test(args...);
}
const LL mod=1e9+7;
const int maxn=3e5+9;
const int inf=0x3f3f3f3f;
LL rd() {
    LL ans=0;
    char last=' ',ch=getchar();
    while(!(ch>='0' && ch<='9'))
        last=ch,ch=getchar();
    while(ch>='0' && ch<='9')
        ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')
        ans=-ans;
    return ans;
}
#define rd read()
/*_________________________________________________________begin*/

namespace Fast_IO{ //orz laofu
    const int MAXL((1 << 18) + 1);int iof, iotp;
    char ioif[MAXL], *ioiS, *ioiT, ioof[MAXL],*iooS=ioof,*iooT=ioof+MAXL-1,ioc,iost[55];
    char Getchar(){
        if (ioiS == ioiT){
            ioiS=ioif;ioiT=ioiS+fread(ioif,1,MAXL,stdin);return (ioiS == ioiT ? EOF : *ioiS++);
        }else return (*ioiS++);
    }
    void Write(){fwrite(ioof,1,iooS-ioof,stdout);iooS=ioof;}
    void Putchar(char x){*iooS++ = x;if (iooS == iooT)Write();}
    inline int read(){
        int x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    inline long long read_ll(){
        long long x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    void Getstr(char *s, int &l){
        for(ioc=Getchar();ioc==' '||ioc=='\n'||ioc=='\t';)ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(l=0;!(ioc==' '||ioc=='\n'||ioc=='\t'||ioc==EOF);ioc=Getchar())s[l++]=ioc;s[l] = 0;
    }
    template <class Int>void Print(Int x, char ch = '\0'){
        if(!x)Putchar('0');if(x<0)Putchar('-'),x=-x;while(x)iost[++iotp]=x%10+'0',x/=10;
        while(iotp)Putchar(iost[iotp--]);if (ch)Putchar(ch);
    }
    void Putstr(const char *s){for(int i=0,n=strlen(s);i<n;++i)Putchar(s[i]);}
} // namespace Fast_IO
using namespace Fast_IO;

namespace LCT {
struct node {
    int f, son[2] ;
    bool fz ;
} tr[maxn] ;

inline void init(int n){
    rep(i,0,n)tr[i].f=tr[i].son[0]=tr[i].son[1]=tr[i].fz=0;
}

inline void reverse ( int x ) {
    tr[x].fz = 0 ;
    swap ( tr[x].son[0], tr[x].son[1] ) ;
    int lc = tr[x].son[0] ;
    int rc = tr[x].son[1] ;
    tr[lc].fz ^= 1, tr[rc].fz ^= 1 ;
}

inline void rotate ( int x, int w ) {
    int f = tr[x].f, ff = tr[f].f, r, R ;
    r = tr[x].son[w] ;
    R = f ;
    tr[R].son[1-w] = r ;
    if ( r )
        tr[r].f = R ;
    r = x ;
    R = ff ;
    if ( tr[R].son[0] == f )
        tr[R].son[0] = r ;
    else if ( tr[R].son[1] == f )
        tr[R].son[1] = r ;
    tr[r].f = R ;
    r = f ;
    R = x ;
    tr[R].son[w] = r ;
    tr[r].f = R ;
}

int tmp[maxn] ;

inline void splay ( int x, int rt ) {
    int s = 0, i = x ;
    while ( tr[i].f && (tr[tr[i].f].son[0]==i||tr[tr[i].f].son[1]==i) ) {
        tmp[++s] = i ;
        i = tr[i].f ;
    }
    tmp[++s] = i ;
    while ( s ) {
        i = tmp[s] ;
        s -- ;
        if ( tr[i].fz )
            reverse(i) ;
    }
    while ( tr[x].f!=rt && (tr[tr[x].f].son[0]==x||tr[tr[x].f].son[1]==x) ) {
        int f = tr[x].f, ff = tr[f].f ;
        if ( ff == rt || (tr[ff].son[0]!=f&&tr[ff].son[1]!=f) ) {
            if ( x == tr[f].son[0] )
                rotate(x,1) ;
            else
                rotate(x,0) ;
        } else {
            if ( tr[ff].son[0] == f && tr[f].son[0] == x )
                rotate(f,1), rotate(x,1) ;
            else if ( tr[ff].son[1] == f && tr[f].son[1] == x )
                rotate(f,0), rotate(x,0) ;
            else if ( tr[ff].son[0] == f && tr[f].son[1] == x )
                rotate(x,0), rotate(x,1) ;
            else if ( tr[ff].son[1] == f && tr[f].son[0] == x )
                rotate(x,1), rotate(x,0) ;
        }
    }
}

inline void access ( int x ) {
    int y = 0 ;
    while ( x ) {
        splay ( x, 0 ) ;
        tr[x].son[1] = y ;
        if ( y != 0 )
            tr[y].f = x ;
        y = x ;
        x = tr[x].f ;
    }
}

inline void makeroot ( int x ) {
    access(x) ;
    splay(x,0) ;
    tr[x].fz ^= 1 ;
}

inline void link ( int x, int y ) {
    makeroot(x) ;
    tr[x].f = y ;
    access(x) ;
}

inline void cut ( int x, int y ) {
    makeroot(x) ;
    access(y) ;
    splay(y,0) ;
    tr[tr[y].son[0]].f = 0 ;
    tr[y].son[0] = 0 ;
}

int find_root ( int x ) {
    access(x) ;
    splay(x,0) ;
    while ( tr[x].son[0] != 0 )
        x = tr[x].son[0] ;
    return x ;
}
}
using namespace LCT;

int n,m,q;
pill e[maxn];
int ans[maxn];
int len[maxn];
int mi[maxn][30];
void init_ST() {
    rep(i,1,maxn-1){
        len[i]=floor(log2(i));
    }
    int L=len[m];
    rep(i,1,m){
        mi[i][0]=ans[i];
    }
    rep(i,1,L) {
        rep(j,1,m){
            if(j+(1<<i)-1>m)break;
            mi[j][i]=min(mi[j][i-1],mi[j+(1<<i-1)][i-1]);
        }
    }
}
int findMin(int l,int r){
    int L=len[r-l+1];
    return min(mi[l][L],mi[r-(1<<L)+1][L]);
}

int main() {
    int t=rd;
    while(t--){
        int last=0;
        n=rd,m=rd,q=rd;
        init(n);
        rep(i,1,m)e[i]={rd,rd};
        int l=1,r=0;
        while(r<m){
            r++;
            while(find_root(e[r].fi)==find_root(e[r].se)){
                ans[l]=r;
                cut(e[l].fi,e[l].se);
                l++;
            }
            link(e[r].fi,e[r].se);
        }
        rep(i,l,m)
            ans[i]=inf;
        init_ST();
        while(q--){
            int l=(rd^last)%m+1,r=(rd^last)%m+1;
            if(l>r)swap(l,r);
            int Left=findMin(l,r);
            if(Left<=r){
                puts("Yes");
                last=1;
            }
            else{
                puts("No");
                last=0;
            }
        }
    }
    return 0;
}

/*_________________________________________________________end*/