记录编号	367850	评测结果	AAAAAAAAAAAAAAW
题目名称	[WC 2006]水管局长数据加强版	最终得分	93
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	3.178 s
提交时间	2017-02-02 15:40:23	内存使用	19.38 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x)))
#define dir(x) ((x)->p->ch[1]==(x))
using namespace std;
const int maxn=100010,maxe=1000010;
struct node{
	int key,mx,pos;
	bool rev;
	node *ch[2],*p;
	node(int d=0):key(d),mx(d),pos(-1),rev(false){}
	inline void pushdown(){
		if(!rev)return;
		ch[0]->rev^=true;
		ch[1]->rev^=true;
		if(pos!=-1)pos^=1;
		swap(ch[0],ch[1]);
		rev=false;
	}
	inline void refresh(){
		mx=key;
		pos=-1;
		if(ch[0]->mx>mx){
			mx=ch[0]->mx;
			pos=0;
		}
		if(ch[1]->mx>mx){
			mx=ch[1]->mx;
			pos=1;
		}
	}
}null[maxn<<1],*ptr;
struct edge{
	int u,v,w;
	bool operator<(const edge &e)const{return w<e.w;}
}e[maxe];
struct A{int tp,u,v,w;}a[maxn];
void Kruskal();
int findroot(int);
void mergeset(int,int);
void dfs(int);
node *access(node*);
void makeroot(node*);
void link(node*,node*);
void cut(node*,node*);
node *getroot(node*);
node *getmax(node*,node*);
void splay(node*);
void rot(node*,int);
map<node*,pair<node*,node*> >mp;
set<pair<int,int> >del;
map<pair<int,int>,int>w;
int p[maxn];
int n,m,q,ans[maxn];
node *tmp;
int main(){
	freopen("tube_strong.in","r",stdin);
	freopen("tube_strong.out","w",stdout);
	null->ch[0]=null->ch[1]=null->p=null;
	null->mx=1<<31;
	scanf("%d%d%d",&n,&m,&q);
	ptr=null+n;
	for(int i=1;i<=n;i++){
		null[i].ch[0]=null[i].ch[1]=null[i].p=null;
		p[i]=i;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
		if(e[i].u>e[i].v)swap(e[i].u,e[i].v);
		w[make_pair(e[i].u,e[i].v)]=e[i].w;
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d%d",&a[i].tp,&a[i].u,&a[i].v);
		if(a[i].u>a[i].v)swap(a[i].u,a[i].v);
		if(a[i].tp==2){
			a[i].w=w[make_pair(a[i].u,a[i].v)];
			w.erase(make_pair(a[i].u,a[i].v));
			del.insert(make_pair(a[i].u,a[i].v));
		}
	}
	Kruskal();
	for(int i=q;i;i--){
		if(a[i].tp==1)ans[i]=getmax(null+a[i].u,null+a[i].v)->key;
		else{
			tmp=getmax(null+a[i].u,null+a[i].v);
			if(tmp->key<=a[i].w)continue;
			cut(tmp,mp[tmp].first);
			cut(tmp,mp[tmp].second);
			mp[tmp]=make_pair(null+a[i].u,null+a[i].v);
			tmp->key=a[i].w;
			tmp->refresh();
			link(tmp,null+a[i].u);
			link(tmp,null+a[i].v);
		}
	}
	for(int i=1;i<=q;i++)if(a[i].tp==1)printf("%d\n",ans[i]);
	return 0;
}
void Kruskal(){
	int cnt=1;
	node *tmp;
	sort(e+1,e+m+1);
	for(int i=1;i<=m&&cnt<n;i++)if(!del.count(make_pair(e[i].u,e[i].v))&&findroot(e[i].u)!=findroot(e[i].v)){
		cnt++;
		mergeset(e[i].u,e[i].v);
		*(tmp=++ptr)=node(e[i].w);
		tmp->ch[0]=tmp->ch[1]=tmp->p=null;
		link(tmp,null+e[i].u);
		link(tmp,null+e[i].v);
		mp[tmp]=make_pair(null+e[i].u,null+e[i].v);
	}
}
int findroot(int x){return p[x]==x?x:(p[x]=findroot(p[x]));}
inline void mergeset(int x,int y){p[findroot(x)]=findroot(y);}
node *access(node *x){
	node *y=null;
	while(x!=null){
		splay(x);
		x->ch[1]=y;
		(y=x)->refresh();
		x=x->p;
	}
	return y;
}
void makeroot(node *x){
	access(x);
	splay(x);
	x->rev^=true;
}
void link(node *x,node *y){
	makeroot(x);
	x->p=y;
}
void cut(node *x,node *y){
	makeroot(x);
	access(y);
	splay(y);
	y->ch[0]->p=null;
	y->ch[0]=null;
	y->refresh();
}
node *getroot(node *x){
	access(x);
	splay(x);
	while(x->pushdown(),x->ch[0]!=null)x=x->ch[0];
	return x;
}
node *getmax(node *x,node *y){
	makeroot(x);
	x=access(y);
	while(x->pushdown(),x->pos!=-1)x=x->ch[x->pos];
	return x;
}
void splay(node *x){
	x->pushdown();
	while(!isroot(x)){
		if(!isroot(x->p))x->p->p->pushdown();
		x->p->pushdown();
		x->pushdown();
		if(isroot(x->p)){
			rot(x->p,dir(x)^1);
			break;
		}
		if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1);
		else rot(x->p,dir(x)^1);
		rot(x->p,dir(x)^1);
	}
}
void rot(node *x,int d){
	node *y=x->ch[d^1];
	if((x->ch[d^1]=y->ch[d])!=null)y->ch[d]->p=x;
	y->p=x->p;
	if(!isroot(x))x->p->ch[dir(x)]=y;
	(y->ch[d]=x)->p=y;
	x->refresh();
	y->refresh();
}