记录编号	416289	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	Toptree	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.857 s
提交时间	2017-06-20 21:24:47	内存使用	6.60 MiB

#include<cstdio>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
const int N=1e5+10;
struct heap{
	__gnu_pbds::priority_queue<int,greater<int> > Q1,Q2;
	void push(int x){Q1.push(x);}
	void del(int x){Q2.push(x);}
	int top(){
		while (!Q2.empty()&&Q1.top()==Q2.top()) Q1.pop(),Q2.pop();
		return Q1.top();
	}
}H[N];
int fa[N],son[N][2],Min_v[N],Min_H[N],v[N];
int size[N],virt[N],vis[N],tag[N];
//H[x]表示x虚边所连接的子树的大小构成的堆 
//v[x]表示x的点权 
//Min_v[x]表示x所在splay子树中v的最小值 
//Min_H[x]表示x所在splay子树中H的最小值 
//virt[x]表示x虚边所连接的子树中子树大小和 
//size[x]表示x所在splay子树中v和virt的和 
bool root[N],rev[N];
#define lc son[x][0]
#define rc son[x][1]
void update(int x){
	Min_v[x]=v[x];
	Min_H[x]=H[x].top();
	size[x]=virt[x]+1;
	if (lc){
		Min_v[x]=min(Min_v[x],Min_v[lc]);
		Min_H[x]=min(Min_H[x],Min_H[lc]);
		size[x]+=size[lc];
	}
	if (rc){
		Min_v[x]=min(Min_v[x],Min_v[rc]);
		Min_H[x]=min(Min_H[x],Min_H[rc]);
		size[x]+=size[rc];
	}
}
void flip(int x){
	swap(lc,rc);
	rev[x]^=1;
}
void pushdown(int x){
	if (!x) return;
	if (rev[x]){
		if (lc) flip(lc);
		if (rc) flip(rc);
		rev[x]=0;
	}
	if (tag[x]){
		if (lc) vis[lc]=tag[lc]=tag[x];
		if (rc) vis[rc]=tag[rc]=tag[x];
		tag[x]=0;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (son[z][0]==y) son[z][0]=x;else
	if (son[z][1]==y) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	pushdown(x);
	for (;!root[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!root[y]) rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
}
void cut_r(int x){
	int y=rc;
	if (!y) return;
	rc=0;root[y]=1;
	virt[x]+=size[y];
	H[x].push(min(Min_v[y],Min_H[y]));
	update(x);
}
void link_r(int x,int y){
	virt[x]-=size[y];
	H[x].del(min(Min_v[y],Min_H[y]));
	root[rc=y]=0;
	update(x);
}
void access(int x){
	splay(x);
	cut_r(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		cut_r(y);
		link_r(y,x);
		splay(x);
	}
}
void makeroot(int x){
	access(x);
	flip(x);
}
void link(int x,int y){
	makeroot(x);
	access(y);
	fa[x]=y;
	virt[y]+=size[x];
	H[y].push(min(Min_v[x],Min_H[x]));
	update(y);
}
void cut(int x,int y){
	makeroot(y);
	access(x);
	lc=fa[y]=0;root[y]=1;
	update(x);
}
int lca(int w,int x,int y){
	static int C=0;C++;
	makeroot(w);
	access(y);
	vis[y]=tag[y]=C;
	access(x);
	while (1){
		pushdown(x);
		if (rc&&vis[rc]==C) x=rc;else
		if (vis[x]==C) break;
		x=lc;
	}
	splay(x);
	return x;
}
int n,m;
int main()
{
	freopen("toptree.in","r",stdin);
	freopen("toptree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&v[i]);
		H[i].push(1e9);
		root[i]=1;
		update(i);
	}
	while (m--){
		int tp,w,x,y;
		scanf("%d%d%d",&tp,&w,&x);
		if (tp==1) link(w,x);
		if (tp==2) cut(w,x);
		if (tp==3) access(w),v[w]=x,update(w);
		if (tp==4){
			makeroot(w);
			access(x);
			printf("%d\n",Min_v[x]);
		}
		if (tp==5){
			scanf("%d",&y);
			printf("%d\n",lca(w,x,y));
		}
		if (tp==6){
			makeroot(w);
			access(x);
			printf("%d\n",virt[x]+1);
		}
		if (tp==7){
			makeroot(w);
			access(x);
			printf("%d\n",min(v[x],H[x].top()));
		}
	}
	return 0;
}