网上基本上找不到这道题，何况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时间下是不存在的，就不能继续向上找了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,m,c,yr,ang;
int f[];
int sz[];
int t[]; int read()
{
char c=getchar();int ret=;
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')ret=ret*+c-'',c=getchar();
return ret;
} int findfa(int p,int y)
{
while(f[p]!=p&&t[p]<=y)p=f[p];
return p;
} int main()
{
freopen("history.in","r",stdin);
freopen("history.out","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
c=yr=ang=;
for(int i=;i<n;i++)f[i]=i,sz[i]=,t[i]=;
for(int i=;i<=m;i++)
{
char op[];
scanf("%s",op+);
if(op[]=='K')
{
ang=;
c=read();
}
if(op[]=='R')
{
int x=read(),y=read();
if(ang)x=(x+c)%n,y=(y+c)%n;
yr++;
x=findfa(x,yr),y=findfa(y,yr);
if(x==y)continue;
if(sz[x]<sz[y])swap(x,y);
f[y]=x;
sz[x]+=sz[y];
t[y]=yr;
}
if(op[]=='T')
{
int x=read(),y=read(),tt=read();
int nx=findfa(x,yr),ny=findfa(y,yr);
int px=findfa(x,yr-tt),py=findfa(y,yr-tt);
if(px!=py&&nx==ny)printf("Y\n"),ang=;
else printf("N\n"),ang=;
}
}
}
fclose(stdin);
fclose(stdout);
return ;
}
History