【luogu P3377 左偏树（可并堆）】模板

题目连接：https://www.luogu.org/problemnew/show/P3377

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 300001 + 10;

struct Left_Tree{

	int val, fa, son[2], dis;

}h[maxn<<2];

int n, m;

int Merge(int r1, int r2)

{

	if(r1 == 0 || r2 == 0) return r1 + r2;

	if(h[r1].val > h[r2].val) swap(r1, r2);

	h[r1].son[1] = Merge(h[r1].son[1], r2);

	h[h[r1].son[1]].fa = r1;

	if(h[h[r1].son[0]].dis < h[h[r1].son[1]].dis) swap(h[r1].son[0], h[r1].son[1]);

	h[r1].dis = h[h[r1].son[1]].dis + 1;

	return r1;

}

void destory(int r1)

{

	h[r1].val = -1;

	h[h[r1].son[0]].fa = h[h[r1].son[1]].fa = 0;

	Merge(h[r1].son[0], h[r1].son[1]);

}

int find(int x)

{

	while(h[x].fa)

		x = h[x].fa;

	return x;

}

int main()

{

	scanf("%d%d",&n,&m);

	//h[0].dis = -1;

	for(int i = 1; i <= n; i++)

	scanf("%d",&h[i].val);

	for(int i = 1; i <= m; i++)

	{

		int opt, x, y;

		scanf("%d",&opt);

		if(opt == 1)

		{

			scanf("%d%d",&x,&y);

			if(h[x].val == -1 || h[y].val == -1) continue;

			int t1 = find(x), t2 = find(y);

			if(t1 != t2)

			Merge(t1, t2);

		}

		else

		{

			scanf("%d",&x);

			if(h[x].val == -1) printf("-1\n");

			else

			{

				int t1 = find(x);

				printf("%d\n",h[t1].val);

				destory(t1);

			}

		}

	}

	return 0;

}

巴特西

【luogu P3377 左偏树（可并堆）】模板

最新文章

热门文章

巴特西

【luogu P3377 左偏树（可并堆）】 模板

最新文章

热门文章

【luogu P3377 左偏树（可并堆）】模板