左偏树求条玄关

#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
const int maxn=1e5+10;
struct node
{
	int data,id;
	int lc=-1,rc=-1;
}tree[maxn];
int n,m;
bool operator<(const node& a,const node& b)
{
	if(a.data==b.data)
	{
		return a.id<b.id;
	}
	return a.data<b.data;
}
int fa[maxn];
int tx[maxn];
int ds[maxn];
bool is_del[maxn];
int merge(int,int);
int finf(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=finf(fa[x]);
}
bool add(int x,int y)
{
	
	if(is_del[x]||is_del[y])
	{
		return 0;
	}
	
	x=tx[x];
	y=tx[y];
	
	x=finf(x);
	y=finf(y);
	if(x==y)
	{
		return 0;
	}
	int t=merge(x,y);//if(x<0||y<0||t<0)throw"";
	fa[x+y-t]=t;
}
int merge(int x,int y)//x,y为根 
{
	if(tree[y]<tree[x])
	{
		swap(x,y);
	}
	if(tree[x].lc==-1)
	{
		tree[x].lc=y;
		ds[x]=1;
		return x;
	}
	if(tree[x].rc==-1)
	{
		tree[x].rc=y;
	}
	else
	{
		tree[x].rc=merge(tree[x].rc,y);
	}
	if(ds[tree[x].lc]<ds[tree[x].rc])
	{
		swap(tree[x].lc,tree[x].rc);
	}
	ds[x]=ds[tree[x].rc]+1;
	return x;
}
pair<bool,int> del(int p)
{
	if(is_del[p])
	{
		return make_pair(false,0);
	}
	p=tx[p];
	p=finf(p);
	is_del[tree[p].id]=1;
	int yy=tree[p].data;
	int x=tree[p].lc,y=tree[p].rc;
	int t;
	if(y!=-1)
	{
		t=merge(x,y);//if(x<0||y<0||t<0)throw"";
	}
	else if(x!=-1)
	{
		t=y;
	}
	else
	{
		return make_pair(true,yy);
	}
	swap(tree[t],tree[p]);
	tx[tree[p].id]=p;
	return make_pair(true,yy);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		fa[i]=tx[i]=i;
		is_del[i]=0;
		ds[i]=1;
		scanf("%d",&tree[i].data);
		tree[i].id=i;
	}
	while(m--)
	{
		int op,x,y;
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d",&x,&y);
			add(x,y);
		}
		else
		{
			scanf("%d",&x);
			pair<bool,int> pr=del(x);
			if(!pr.first)
			{
				printf("%d\n",-1);
			}
			else
			{
				printf("%d\n",pr.second);
			}
		}
	}
	return 0;
}