評測記錄

代碼

#include<bits/stdc++.h>
using namespace std;
bool 人心中的成見是一座大山[300030];
int n,m,任你怎么努力都休想搬動;
struct 小爺是魔那又如何 {int l,r,fa,sui,xu,v,x;bool lan;} t[300030];
void 哪吒(int o)
{
	if(t[o].lan) swap(t[o].l,t[o].r),t[t[o].l].lan^=1,t[t[o].r].lan^=1,t[o].lan=0;
}
void 敖丙(int o)
{
	t[o].x=t[o].v^t[t[o].l].x^t[t[o].r].x;
	if(t[o].l) t[t[o].l].fa=o;
	if(t[o].r) t[t[o].r].fa=o;
}
int 助我破鼎(int x,int y)
{
	if(!x||!y) return x+y;
	if(t[x].sui<t[y].sui) return 哪吒(x),t[x].r=助我破鼎(t[x].r,y),敖丙(x),x;
	else return 哪吒(y),t[y].l=助我破鼎(x,t[y].l),敖丙(y),y;
}
bool 天雷滾滾我好怕怕(int o) {return (t[t[o].fa].l!=o&&t[t[o].fa].r!=o)||!t[o].fa;}
int 劈得我渾身掉渣渣(int o)
{
	任你怎么努力都休想搬動=0;
	while(!天雷滾滾我好怕怕(o)) 人心中的成見是一座大山[++任你怎么努力都休想搬動]=(t[t[o].fa].l==o),o=t[o].fa;
	return o;
}
void 突破天劫我笑哈哈(int o,int &l,int &r)
{
	if(!任你怎么努力都休想搬動) return 哪吒(o),l=o,r=t[o].r,t[o].r=0,敖丙(o),void();
	bool d=人心中的成見是一座大山[任你怎么努力都休想搬動--];
	d^=t[o].lan,哪吒(o);
	if(d) r=o,突破天劫我笑哈哈(t[o].l,l,t[o].l);
	else l=o,突破天劫我笑哈哈(t[o].r,t[o].r,r);
	敖丙(o);
}
int 逆天改命我吹喇叭(int o)
{
	o=劈得我渾身掉渣渣(o),哪吒(o);
	while(t[o].l) o=t[o].l,哪吒(o);
	return o;
}
int 去你的鳥命(int o)
{
	int last=0;
	while(o)
	{
		int shang,xia;
		突破天劫我笑哈哈(劈得我渾身掉渣渣(o),shang,xia);
		t[逆天改命我吹喇叭(last)].xu=0;
		last=助我破鼎(shang,last);
		t[逆天改命我吹喇叭(xia)].xu=o;
		o=t[逆天改命我吹喇叭(last)].xu;
	}
	return last;
}
int 若前方無路(int o) {return 逆天改命我吹喇叭(去你的鳥命(o));}
void 我便踏出一條路(int o) {t[去你的鳥命(o)].lan^=1;}
void 若天理不容(int x,int y) {我便踏出一條路(x),t[x].xu=y;}
void 我便逆轉這乾坤(int x,int y) {我便踏出一條路(x),去你的鳥命(y),去你的鳥命(x),t[y].xu=0;}
int 我命由我不由天(int x,int y) {return 我便踏出一條路(x),去你的鳥命(y),t[劈得我渾身掉渣渣(y)].x;}
void 我乃吒三太子(int o,int v)
{
	int o1,o2;
	我便踏出一條路(o);
	突破天劫我笑哈哈(劈得我渾身掉渣渣(o),o1,o2);
	t[o].v=v,助我破鼎(o1,o2);
}
void 能降妖來會作詩(int &x)
{
	x=0;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i) 能降妖來會作詩(t[i].v),t[i].x=t[i].v,t[i].sui=rand();
	for(int i=1,op,x,y;i<=m;i++)
	{
		能降妖來會作詩(op),能降妖來會作詩(x),能降妖來會作詩(y);
		if(op==0) printf("%d\n",我命由我不由天(x,y));
		else if(op==1&&若前方無路(x)!=若前方無路(y)) 若天理不容(x,y);
		else if(op==2) 我便逆轉這乾坤(x,y);
		else if(op==3) 我乃吒三太子(x,y);
	}
	return 0;
}