history 题解（并查集）

考虑使用边带权并查集维护点之间的连通性，边权为这条边建立的时间，查询时如果查询时间小于边权则不能通行（巧妙地处理了时间的性质）。

由于时间这种东西性质特殊无法路径压缩，所以使用按秩合并。

code：

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define debug cout<<"DEBUG"<<endl;
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define imp map<int,int>
using namespace std;
const int N=3e5+5;
int n,m,fa[N],d[N],siz[N],tim,c;
bool op;
void merge(int x,int y){
	if(siz[x]>siz[y]){
		swap(x,y);
	}
	fa[x]=y;
	d[x]=tim;
	siz[y]+=siz[x];
}
int find(int x,int t){
	f(fa[x]==x||d[x]>t) return x;
	return find(fa[x],t);
}
int main(){
	freopen("history.in","r",stdin);
	freopen("history.out","w",stdout);
	while(cin>>n>>m){
		op=0;
		c=0;
		tim=0;
		for(int i=0;i<=n;i++){
			fa[i]=i;
			siz[i]=1;
			d[i]=0;
		}
		while(m--){
			char sc[5];
			scanf("%s",sc+1);
			if(sc[1]=='K'){
				op=0;
				scanf("%d",&c);
			}
			if(sc[1]=='R'){
				tim++;
				int x,y;
				scanf("%d%d",&x,&y);
				if(op){
					x=(x+c)%n;
					y=(y+c)%n;
				}
				int fx=find(x,tim);
				int fy=find(y,tim);
				if(fx!=fy){
					merge(fx,fy);
				}
			}
			if(sc[1]=='T'){
				int x,y,z;
				scanf("%d%d%d",&x,&y,&z);
				int nx=find(x,tim);
				int ny=find(y,tim);
				int ox=find(x,tim-z);
				int oy=find(y,tim-z);
				if(ox!=oy&&nx==ny){
					op=0;
					printf("Y\n");
				}else{
					op=1;
					printf("N\n");
				}
			}
		}
	}
	return 0;
}