网上基本上找不到这道题，何况LJJ还稍微改了一下......
原题：传送门
题目描述
ljj 被S 国数不清的漂亮小姐姐所吸引，为了搞清楚为什么S 国有如此多的漂亮小姐姐，他决定研究S 国的历史。
根据S 国史书的记载，在史书记载前，S 国有n 个城市(城市编号0~n-1)，它们彼此之间都没有道路相连，但一个城市内是联通的。
每一年，在位的国王会在城市x,y 之间修建一条双向道路，一条道路可能被修建多次，但修建双向道路的起点和终点不会是同一个城市。
而在这之间，国王会计划进行若干次旅行。对于计划进行的一次旅行st->ed，
如果当时能完成这次旅行。而t 年前不能完成这次旅行，国王会对之前的建设成果感到满意，
否则他会很生气，并改变接下来所有计划修建的道路，即让实际修建的道路的x,y 更换为(x+c)%n，(y+c)%n，
生气状态持续到下一次旅行开始，旅行的起点和终点可能是同一个城市。
当然这些年中也发生了若干次国王的交替，初始国王的c 值为0，而之后每个国王的c 值不一定相同。
一个国王在位期间，他的c 值不会改变，刚登基的国王处于不生气的状态。
请根据史书帮助ljj 得出国王对于每次旅行是否满意，如果你全部分析正确的话，他说不定会给你介绍一个漂亮的小姐姐呢。
输入
本题含有多组测试数据！
对于每组数据第一行两个整数n,m 表示城市数和史书记载的内容数。
接下来m 行，每行是以下三种格式之一：
1.K c，表示国王交替，以及新国王的c 值(含义如题目所述)。
2.R x y，表示国王计划在x,y 之间修建一条双向道路，但可能会因为国王生气，并不会在x,y 之间修建道路，具体见题目描述。
3.T st ed t，表示国王计划进行一次从st 到ed 的旅行，且比较的是t 年前的情况(国王可能会史书开始记载以前的情况比较)。
注意只有遇到R 操作才会使实际年份+1。
输出
对于每个T 操作输出一行，如果国王满意输出Y，否则输出N。
样例输入1
3 7
R 0 1
T 0 1 1
K 1
R 0 1
T 0 1 1
R 0 1
T 0 2 1
样例输出1
Y
N
Y
数据范围与约定
对于30%的数据，1<=n<=1000，1<=m<=3000。
另30%数据满足没有任何国王交替。
对于100%的数据，满足1<=n,m<=3*10^5，0<= v,x,y,st,ed <n，0<= t <m。
数据有一定梯度，每个测试点数据组数<=3
题解
这道题做法有很多。
我第一眼看还以为是可持久化并查集，果断打了暴力......
显然可以离线做，但是这道题仅仅是修改强制在线。
如果是询问也强制在线，就不能离线做了。
正解其实是并查集按秩合并。
由于是按秩合并，每个点的父亲只会被修改一次（从它自己变成另一个点）。
所以记录一下父亲被更改的时间。
找祖先的时候，给一个时间限制y，如果t[i]>y，则那个连接实际上在y时间下是不存在的，就不能继续向上找了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int n,m,c,yr,ang; 7 int f[300005]; 8 int sz[300005]; 9 int t[300005]; 10 11 int read() 12 { 13 char c=getchar();int ret=0; 14 while(c<'0'||c>'9')c=getchar(); 15 while(c>='0'&&c<='9')ret=ret*10+c-'0',c=getchar(); 16 return ret; 17 } 18 19 int findfa(int p,int y) 20 { 21 while(f[p]!=p&&t[p]<=y)p=f[p]; 22 return p; 23 } 24 25 int main() 26 { 27 freopen("history.in","r",stdin); 28 freopen("history.out","w",stdout); 29 while(scanf("%d%d",&n,&m)!=EOF) 30 { 31 c=yr=ang=0; 32 for(int i=0;i<n;i++)f[i]=i,sz[i]=1,t[i]=0; 33 for(int i=1;i<=m;i++) 34 { 35 char op[5]; 36 scanf("%s",op+1); 37 if(op[1]=='K') 38 { 39 ang=0; 40 c=read(); 41 } 42 if(op[1]=='R') 43 { 44 int x=read(),y=read(); 45 if(ang)x=(x+c)%n,y=(y+c)%n; 46 yr++; 47 x=findfa(x,yr),y=findfa(y,yr); 48 if(x==y)continue; 49 if(sz[x]<sz[y])swap(x,y); 50 f[y]=x; 51 sz[x]+=sz[y]; 52 t[y]=yr; 53 } 54 if(op[1]=='T') 55 { 56 int x=read(),y=read(),tt=read(); 57 int nx=findfa(x,yr),ny=findfa(y,yr); 58 int px=findfa(x,yr-tt),py=findfa(y,yr-tt); 59 if(px!=py&&nx==ny)printf("Y\n"),ang=0; 60 else printf("N\n"),ang=1; 61 } 62 } 63 } 64 fclose(stdin); 65 fclose(stdout); 66 return 0; 67 }
