2019.8.23
3.1 题目描述
历史学家小Ａ正在研究一个奇怪的王国的历史。当前阶段的任务是研究该国的交通。根据这个奇怪的王国的史书记载，史书开始记载前这个王国有 n 个城市（城市从 0 开
始标号），但所有城市之间都没有道路相连。
每一年，在位的国王会修建一条 x 到 y 的双向道路，一条道路可能被修建多次，但不会修建起点和终点为同一个城市的道路。
而在这之间，国王会计划进行若干次旅行。对于计划进行的一次旅行 st->ed，如果当时能完成这次旅行，而 t 年前不能完成这次旅行，那么国王会对之前的建设成果感到满意， 否则他会很生气，并在下一次计划旅行前都让史官记录下错误的修建道路的信息，即把 x、y 记作(x+n-c) mod n，(y+n-c) mod n。
当然在这些年中也发生了若干次国王的交替，初始国王的 c 值为 0，而每个国王的 c 值不一定相同，但在国王在位期间 c 值不会改变，新上位的国王开始处于不生气的状态。
请根据史书帮助小 A 得出国王每次对于计划旅行是否满意，从而辅助小 A 能够研究该国的交通信息。
3.2 输入格式
第一行为两个整数 n，m，表示初始城市数和历史书记载的内容数。接下来 m 行，每行是以下三种格式之一：
-
K v ：表示国王交替，新国王的 c 值为 v
-
R x y：表示史书上记载的是国王修建了 x 到 y 的双向道路，但注意这个记录的可能不是实际状况。
-
T st ed t：表示国王计划进行的一次 st->ed 的旅行，且比较的是 t 年前的情况（国王可能会和史书开始记载以前的情况比较），注意这个记录的肯定是实际情况。
注意只有遇到 R 操作才会使年份的计数+1。
3.3 输出格式
输对于每个 T 的记录输出一行，如果此次计划旅行令国王满意，则输出 Y，否则输出 X。
3.4 样例输入
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
3.5 样例输出
Y N Y
3 .6 数据范围与约定
对于 30％的数据，保证 n<=1000 ,m<=3000。另 30％的数据满足没有发生国王的交替。
对于 100％的数据，保证 n，m<=300000，0<=v，x，y，st，ed<n，0<=t<m。数据有梯度
题目所求的是两个点的连通性，可以用并查集很好地维护。
要求询问历史版本，可持久化并查集？其实没这个必要，考虑到只是求历史版本的值，而不是真正地变成历史状态，所以可以预先在之前访问历史版本的时候就把现在的问题求解出来，在当前查询的时候就可以直接调用了，因为要预处理所以考虑离线。（细节有点多）
Code：
#include<stdio.h>
#define N 300007
char op[N];
int a[N],b[N],c[N],n,m,head[N],cnt=1,sta[N],t,fa[N];
bool flag[N],tag;
inline int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
struct E{
int next,to;
}e[N<<1];
template<class T>
inline void read(T &x){
x=0;int flag=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
x*=flag;
}
inline int max(int x,int y){return x>y? x:y;}
inline void read_char(char &x){
x=getchar();
while(x<'A'||x>'Z') x=getchar();
}
inline void add(int id,int to){
e[++cnt]=(E){head[id],to};
head[id]=cnt;
}
inline void dfs(int u){
if(u>m) return ;
if(op[u]=='K') tag=0;
if(op[u]=='R'){
int x=a[u],y=b[u];
if(tag){
x=((x-1)%n+n+c[u])%n+1;
y=((y-1)%n+n+c[u])%n+1;
}
int fa_x=find(x),fa_y=find(y);
fa[fa_y]=fa_x;
}
if(op[u]=='T') flag[u]^=(find(a[u])==find(b[u])),tag=flag[u]^1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
flag[v]=(find(a[v])==find(b[v]));
}
dfs(u+1);
}
int main(){
freopen("history.in","r",stdin);
freopen("history.out","w",stdout);
read(n);read(m);
for(int i=1;i<=n;i++) fa[i]=i;
int qwq;
for(int i=1;i<=m;i++){
read_char(op[i]);
if(op[i]=='K') read(c[i]);
else c[i]=c[i-1];
if(op[i]=='R') read(a[i]),read(b[i]),sta[++t]=i;
else if(op[i]=='T') read(a[i]),read(b[i]),read(qwq),add(sta[max(0,t-qwq)],i);
a[i]++,b[i]++;
}
dfs(0);
for(int i=1;i<=m;i++)
if(op[i]=='T') printf("%c\n",flag[i]? 'Y':'N');
}