「广州集训 Day3」历史 - LCT/并查集

题目大意

历史学家$dhh$正在研究一个奇怪的王国的历史。当前阶段的任务是研究该国的交通。
根据这个奇怪的王国的史书记载，史书开始记载前这个王国有$n$个城市（城市从$0$开始标号），但所有城市之间都没有道路相连。
每一年，在位的国王会修建一条双向道路$x\rightarrow y$，一条道路可能被修建多次。
而在这之间，国王会计划进行若干次旅行。对于计划进行的一次旅行$st\rightarrow ed$，如果当时能完成这次旅行，而$t$年前不能完成这次旅行，那么国王会对之前的建设成果感到满意，否则他会很生气，并在他感到满意之前（包括使他满意的那次旅行）都让史官记录下错误的信息，怎么样得到正确信息将在输入格式中描述。
当然在这些年中也发生了若干次国王的交替，而每个国王的$c$值不一定相同，但在国王在位期间$c$值不会改变（初始国王的$c$值为$0$，其他的$c$值可通过记载得到），新上位的国王开始处于不生气的状态。
请根据史书帮助$dhh$得出国王每次对于计划旅行是否满意，从而使$dhh$能够研究该国的交通。

---

题目分析

poj的一次比赛原题啊~
加密规则贼麻烦啊~

查询连通性与历史版本连通性，第一眼这不是可持久化并查集吗？
当然可持久化并查集是可以做的，因为只有两种操作，于是我们可以用按秩合并并查集（不路径压缩）来水过这道题。

那这样A题不就太没意思了吗？
有没有注意到这道题有点类似水管局长？
维护历史版本连通性相当于在生成树上查询一条路径上的最晚修建的边？

这不是动态树解决的问题吗？
贴个版就可以过了。
动态树真的不难，动态树真的不难，动态树真的不难！

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=300005;
struct Tree {
	int father,child[2];
	bool rev;
	int max,val;
};
struct Link_Cut_Tree {
	Tree tree[maxn*2];
	stack<int>S;
	void init() {
		for(int i=0; i<=maxn; i++)tree[i].max=tree[i].val=-0x7fffffff/2;
	}
	#define ls(x) tree[x].child[0]
	#define rs(x) tree[x].child[1]
	#define fa(x) tree[x].father
	#define rev(x) tree[x].rev
	bool isroot(int index) {
		return ls(fa(index))!=index&&rs(fa(index))!=index;
	}
	bool checkson(int index) {
		return rs(fa(index))==index;
	}
	void push_down(int index) {
		if(!rev(index))return;
		swap(ls(index),rs(index));
		rev(ls(index))^=1;
		rev(rs(index))^=1;
		rev(index)=0;
	}
	void push_up(int index) {
		tree[index].max=max(max(tree[ls(index)].max,tree[rs(index)].max),tree[index].val);
	}
	void rotate(int index) {
		int father=fa(index),grand=fa(father),side=checkson(index);
		if(!isroot(father))tree[grand].child[checkson(father)]=index;
		tree[father].child[side]=tree[index].child[side^1];
		fa(tree[father].child[side])=father;
		fa(father)=index;
		tree[index].child[side^1]=father;
		fa(index)=grand;
		push_up(father);
		push_up(index);
	}
	void splay(int index) {
		S.push(index);
		for(int i=index; !isroot(i); i=fa(i))S.push(fa(i));
		while(!S.empty())push_down(S.top()),S.pop();
		for(int father; !isroot(index); rotate(index)) {
			father=fa(index);
			if(!isroot(father))rotate(checkson(index)==checkson(father)?father:index);
		}
	}
	void access(int index) {
		for(int son=0; index; son=index,index=fa(index)) {
			splay(index);
			rs(index)=son;
			push_up(index);
		}
	}
	void reverse(int index) {
		access(index);
		splay(index);
		rev(index)^=1;
	}
	void link(int x,int y) { //private
		reverse(x);
		fa(x)=y;
	}
	void split(int x,int y) {
		reverse(x);
		access(y);
		splay(y);
	}
	void link(int index,int x,int y,int val) { //index:num for edge
		link(x,index);
		link(index,y);
		tree[index].val=tree[index].max=val;
	}
	int get_root(int index) {
		access(index);
		splay(index);
		int u=index;
		while(ls(u))u=ls(u);
		return u;
	}
} lct;
int n,cnt,m,year=0;
bool angry;
LL c;
int main() {
	while(~scanf("%d%d",&n,&m)) {
		cnt=n;
		lct.init();
		c=angry=year=0;
		for(int i=1; i<=m; i++) {
			char opt=' ';
			while(opt!='R'&&opt!='K'&&opt!='T')opt=getchar();
			if(opt=='K') {
				LL v=Get_Int();
				c=c*angry+v;
				angry=0;
			} else if(opt=='R') {
				LL x,y;
				x=(Get_Int()+c*angry)%n+1,y=(Get_Int()+c*angry)%n+1;
				year++;
				if(lct.get_root(x)==lct.get_root(y))continue;
				lct.link(++cnt,x,y,year);
			} else {
				LL x,y,v;
				x=(Get_Int()+c*angry)%n+1,y=(Get_Int()+c*angry)%n+1,v=(Get_Int()+c*angry)%n;
				if(lct.get_root(x)!=lct.get_root(y)) {
					puts("N");
					angry=1;
					continue;
				}
				lct.split(x,y);
				if(lct.tree[y].max<=year-v) {
					puts("N");
					angry=1;
				} else {
					puts("Y");
					angry=0;
				}
			}
		}
	}
	return 0;
}