WTRC's Memory

• Codeforces633C​

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=100005,M=1000005,Q=100005;
int n,m,q;
struct Edge{
	int u,v,w,idx;
	bool del;
}e[M];
bool cmp1(const Edge &a,const Edge &b){return a.u==b.u?a.v<b.v:a.u<b.u;}
bool cmp2(const Edge &a,const Edge &b){return a.w<b.w;}
struct Task{
	int op,x,y;
}md[Q];
struct SplayTree *null;
struct SplayTree{
	SplayTree *Fa,*Ls,*Rs,*Mx;
	int Val;
	bool Rev;
	bool Top(){return Fa==null || (Fa->Ls!=this&&Fa->Rs!=this);}
	void PushDown(){
		if (this==null) return;
		if (Rev){Rev=0;Ls->Rev^=1;Rs->Rev^=1;swap(Ls,Rs);}
	}
	void Update(){
		if (this==null) return;
		if (this-null>n) Mx=this;else Mx=null;
		if (Ls->Mx->Val>Mx->Val) Mx=Ls->Mx;
		if (Rs->Mx->Val>Mx->Val) Mx=Rs->Mx;
	}
	void Zig(){
		if (this==null) return;
		SplayTree *y=Fa,*z=y->Fa;
		if (z->Ls==y) z->Ls=this;else if (z->Rs==y) z->Rs=this;Fa=z;
		y->Ls=Rs;if (Rs!=null) Rs->Fa=y;
		Rs=y;y->Fa=this;y->Update();
	}
	void Zag(){
		if (this==null) return;
		SplayTree *y=Fa,*z=y->Fa;
		if (z->Ls==y) z->Ls=this;else if (z->Rs==y) z->Rs=this;Fa=z;
		y->Rs=Ls;if (Ls!=null) Ls->Fa=y;
		Ls=y;y->Fa=this;y->Update();
	}
}a[N+M],*S[N+M],*now;
int Top=0;
void Splay(SplayTree *x){
	now=x;while (!now->Top()) S[++Top]=now,now=now->Fa;
	now->PushDown();while (Top) S[Top--]->PushDown();
	while (!x->Top()){
		SplayTree *y=x->Fa,*z=y->Fa;
		if (!y->Top())
			if (z->Ls==y) if (y->Ls==x) y->Zig(),x->Zig();else x->Zag(),x->Zig();
				else if (y->Rs==x) y->Zag(),x->Zag();else x->Zig(),x->Zag();
		else if (y->Ls==x) x->Zig();else x->Zag(); 
	}
	x->Update();
}
SplayTree *Access(SplayTree *x){
	SplayTree *y=null;
	while (x!=null){
		Splay(x);
		x->Rs=y;x->Update();
		y=x;x=x->Fa;
	}
	return y;
}
void ChangeRoot(SplayTree *x){
	Access(x)->Rev^=1;
	Splay(x);
}
SplayTree *GetRoot(SplayTree *x){
	Access(x);Splay(x);
	x->PushDown();
	while (x->Ls!=null) x=x->Ls,x->PushDown();
	return x;
}
SplayTree *QueryMax(SplayTree *x,SplayTree *y){
	ChangeRoot(x);
	Access(y),Splay(y);
	return y->Mx;
}
void Link(SplayTree *x,SplayTree *y){
	ChangeRoot(x);x->Fa=y;
}
void Cut(SplayTree *x,SplayTree *y){
	ChangeRoot(y);
	Access(x),Splay(x);
	x->Ls->Fa=null;
	x->Ls=null;
}
void Delete(int u,int v){
	int l=1,r=m;
	while (l<r){
		int mid=l+r>>1;
		if (e[mid].u<u ||(e[mid].u==u&&e[mid].v<v)) l=mid+1;
			else r=mid;
	}
	while (l<=m&&e[l].u==u&&e[l].v==v) e[l].del=1,l++;
}
void Recover(int u,int v){
	int l=1,r=m;
	while (l<r){
		int mid=l+r>>1;
		if (e[mid].u<u ||(e[mid].u==u&&e[mid].v<v)) l=mid+1;
			else r=mid;
	}
	while (l<=m&&e[l].u==u&&e[l].v==v){
		int u=e[l].u,v=e[l].v,w=e[l].w;
		SplayTree *t=QueryMax(a+u,a+v);
		if (t->Val>w){
			Cut(t,a+e[t-null-n].v);
			Cut(t,a+e[t-null-n].u);
		}
		else{l++;continue;}
		a[n+l].Val=w,a[n+l].Mx=a+n+l,a[n+l].Rev=0;
		Link(a+u,a+n+l),Link(a+v,a+n+l);
		l++;
	}
}
int cnt,Ans[Q],fa[N],SZ[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	n=IN(),m=IN(),q=IN();
	Rep(i,1,m){
		e[i].u=IN(),e[i].v=IN(),e[i].w=IN(),e[i].del=0;
		if (e[i].u>e[i].v) swap(e[i].u,e[i].v);
	}
	sort(e+1,e+m+1,cmp1);
	Rep(i,1,m) e[i].idx=i;
	Rep(i,1,q){
		md[i].op=IN(),md[i].x=IN(),md[i].y=IN();
		if (md[i].op==2){
			if (md[i].x>md[i].y) swap(md[i].x,md[i].y);
			Delete(md[i].x,md[i].y);
		}
	}
	null=a;
	Rep(i,0,n+m) a[i]=(SplayTree){null,null,null,null,-oo,0};
	sort(e+1,e+m+1,cmp2);
	Rep(i,1,n) fa[i]=i,SZ[i]=1;
	int now=0;
	Rep(i,1,m){
		if (e[i].del) continue;
		int u=e[i].u,v=e[i].v,w=e[i].w,id=e[i].idx;
		int fu=find(u),fv=find(v);
		if (fu!=fv){
			a[n+id].Val=w,a[n+id].Mx=a+n+id,a[n+id].Rev=0;
			Link(a+u,a+n+id),Link(a+v,a+n+id);
			if (SZ[fv]<SZ[fu]) fa[fv]=fu,SZ[fv]+=SZ[fu];else fa[fu]=fv,SZ[fu]+=SZ[fv];
			now++;if (now==n-1) break;
		}
	}
	sort(e+1,e+m+1,cmp1);
	Drp(i,q,1){
		int x=md[i].x,y=md[i].y;
		if (md[i].op==1) Ans[++cnt]=QueryMax(a+x,a+y)->Val;
		else Recover(x,y);
	}
	Drp(i,cnt,1) Out(Ans[i]),putchar('\n');
}