题目描述

历史学家小Ａ正在研究一个奇怪的王国的历史。当前阶段的任务是研究该国的交通。

根据这个奇怪的王国的史书记载，史书开始记载前这个王国有 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 能够研究该

国的交通信息。

输入格式

第一行为两个整数 n，m，表示初始城市数和历史书记载的内容数。

接下来 m 行，每行是以下三种格式之一：

1 . K v ：表示国王交替，新国王的 c 值为 v

2 . R x y：表示史书上记载的是国王修建了 x 到 y 的双向道路，但注意这个记录的可

能不是实际状况。

3 . T st ed t： 表示国王计划进行的一次 st->ed 的旅行， 且比较的是 t 年前的情况 （国

王可能会和史书开始记载以前的情况比较） ，注意这个记录的肯定是实际情况。

注意只有遇到 R 操作才会使年份的计数+1。

输出格式

输对于每个 T 的记录输出一行， 如果此次计划旅行令国王满意， 则输出 Y， 否则输出 X。

样例输入

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

样例输出

Y

N

Y

数据范围与约定

对于 30％的数据，保证 n<=1000 ,m<=3000。

另 30％的数据满足没有发生国王的交替。

对于 100％的数据，保证 n，m<=300000，0<=v，x，y，st，ed < n，0<=t< m。

数据有梯度

离线每次询问都建立一个并查集，会超时。

正解做法：

在并查集上加上一个参数为时间，记录x与它的父亲连接的时间，那么这样就不能路径压缩了。

为了避免超时，我们需要按秩合并，将规模小的并查集合并到规模大的并查集上。

此题需要注意一个问题，城市的序号是从0开始的，在样例中可以看出来。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 300009using namespace std;int n,m,c,f[N],year[N],size[N],tim;bool angry;int find(int x,int t){ while(x!=f[x]&&year[x]<=t) x=f[x]; return x;}int main(){ scanf("%d%d",&n,&m); c=0;angry=false; for(int i=0;i<=n;i++) f[i]=i,size[i]=1; for(int i=1;i<=m;i++) { char Q[10]; int x,y,z; scanf("%s",Q); if(Q[0]=='K') { cin>>c; angry=false; continue; } if(Q[0]=='R') { scanf("%d%d",&x,&y); if(angry) { if((x+=c)>=n) x-=n; if((y+=c)>=n) y-=n; } tim++; x=find(x,tim),y=find(y,tim); if(x==y) continue; if(size[x]