「HNOI2012」永无乡

传送门

Luogu

解题思路

很容易想到平衡树，然后还可以顺便维护一下连通性，但是如何合并两棵平衡树？

我们采用一种类似于启发式合并的思想，将根节点siz较小的那颗平衡树暴力的合并到另一颗上去。

那么复杂度呢？

由于一个点所在的平衡树在经过这样一次合并之后，根节点的siz至少乘2，所以每一次合并的复杂度是 \(O(n\log n)\) 的，所以整个算法的复杂度也就维持在了 \(O(n\log n)\) 级别，这题就搞定了。

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= (c == '-'), c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

const int _ = 100010;

int n, m, q, rt[_];

inline int findd(int x) { return rt[x] == x ? x : rt[x] = findd(rt[x]); }

int tot, val[_], pri[_], ls[_], rs[_], siz[_];

inline int newnode(int v)

{ return siz[++tot] = 1, pri[tot] = rand(), val[tot] = v, tot; }

inline void pushup(int p) { siz[p] = siz[ls[p]] + siz[rs[p]] + 1; }

inline void split(int p, int v, int& x, int& y) {

	if (!p) return (void) (x = y = 0);

	if (val[p] <= v)

		x = p, split(rs[p], v, rs[p], y);

	else

		y = p, split(ls[p], v, x, ls[p]);

	pushup(p);

}

inline int merge(int x, int y) {

	if (!x || !y) return x + y;

	if (pri[x] < pri[y])

		return rs[x] = merge(rs[x], y), pushup(x), x;

	else

		return ls[y] = merge(x, ls[y]), pushup(y), y;

}

inline int kth(int p, int k) {

	if (siz[ls[p]] + 1 > k) return kth(ls[p], k);

	if (siz[ls[p]] + 1 == k) return p;

	if (siz[ls[p]] + 1 < k) return kth(rs[p], k - siz[ls[p]] - 1);

}

inline void dfs(int x, int& y) {

	if (!x) return;

	dfs(ls[x], y);

	dfs(rs[x], y);

	int a, b;

	split(y, val[x], a, b);

	y = merge(merge(a, x), b);

}

inline int unionn(int x, int y) {

	if (siz[x] > siz[y]) swap(x, y);

	return dfs(x, y), y;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	srand(time(0)), read(n), read(m);

	for (rg int v, i = 1; i <= n; ++i)

		read(v), rt[i] = newnode(v);

	for (rg int x, y, i = 1; i <= m; ++i) {

		read(x), x = findd(x);

		read(y), y = findd(y);

		if (x == y) continue;

		rt[x] = rt[y] = unionn(rt[x], rt[y]);

	}

	read(q);

	char s[5];

	for (rg int x, y, i = 1; i <= q; ++i) {

		scanf("%s", s), read(x), read(y);

		if (s[0] == 'Q') {

			x = findd(x);

			if (siz[x] < y) puts("-1");

			else printf("%d\n", kth(x, y));

		} else {

			x = findd(x), y = findd(y);

			if (x == y) continue;

			rt[x] = rt[y] = unionn(rt[x], rt[y]);

		}

	}

	return 0;

}

完结撒花 \(qwq\)

巴特西

「HNOI2012」永无乡

解题思路

细节注意事项

参考代码

最新文章

热门文章