luoguP3224 [HNOI2012]永无乡

https://www.luogu.org/problemnew/show/P3224

考虑对每个岛维护一颗平衡树，用并查集维护连通性，启发式合并即可

这东西其实是一个大暴力，每次把节点少的平衡树合并到节点多的平衡树里

这样可以保证每个点合并一次树的大小*2，每个点最多被插入 log(n) 次，复杂度正确

我使用了简单好写的 leafy tree 作为平衡树，不喜勿喷

#include <bits/stdc++.h>

#define update(u) if(u -> left -> size) u -> size = u -> left -> size + u -> right -> size, u -> value = u -> right -> value

#define new_Node(a, b, c, d) (&(*st[cnt++] = Node(a, b, c, d)))

#define merge(a, b) new_Node(a -> size + b -> size, b -> value, a, b)

#define ratio 4

using namespace std;

typedef unsigned long long ull;

typedef long long ll;

template <typename _T>

inline void read(_T &f) {

    f = 0; _T fu = 1; char c = getchar();

    while(c < '0' || c > '9') {if(c == '-') fu = -1; c = getchar();}

    while(c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}

    f *= fu;

}

const int N = 300000 + 10;

struct Node {

	int size, value;

	Node *left, *right;

	Node (int a, int b, Node *c, Node *d) : size(a), value(b), left(c), right(d) {}

	Node () {}

}*root[N], *st[N], t[N], *null;

int w[N], v[N], f[N], pre[N], len;

int n, m, q, cnt = 0;

void maintain(Node *u) {

	if(u -> left -> size > u -> right -> size * ratio) u -> right = merge(u -> left -> right, u -> right), st[--cnt] = u -> left, u -> left = u -> left -> left;

	if(u -> right -> size > u -> left -> size * ratio) u -> left = merge(u -> left, u -> right -> left), st[--cnt] = u -> right, u -> right = u -> right -> right;

}

void ins(Node *u, int x) {

	if(u -> size == 1) u -> left = new_Node(1, min(u -> value, x), null, null), u -> right = new_Node(1, max(u -> value, x), null, null);

	else ins(x > u -> left -> value ? u -> right : u -> left, x);

	update(u); maintain(u);

}

int find(Node *u, int x) {

	if(u -> size == 1) return u -> value;

	return x > u -> left -> size ? find(u -> right, x - u -> left -> size) : find(u -> left, x);

}

void dfs(Node *u) {

	if(u == null) return;

	st[--cnt] = u;

	dfs(u -> left);

	if(u -> size == 1) w[++len] = u -> value;

	dfs(u -> right);

}

int Merge(int a, int b) {

	if(root[a] -> size < root[b] -> size) swap(a, b);

	len = 0; dfs(root[b]);

	for(register int i = 1; i < len; i++) {

		ins(root[a], w[i]);

	}

	return a;

}

int find(int x) {

	return f[x] == x ? x : f[x] = find(f[x]);

}

int main() {

	read(n); read(m);

	null = new Node(0, 0, 0, 0);

	for(register int i = 0; i <= 300000; i++) st[i] = &t[i];

	for(register int i = 1; i <= n; i++) root[i] = new Node(1, INT_MAX, null, null), read(v[i]), ins(root[i], v[i]), f[i] = i, pre[v[i]] = i;

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

		int a, b;

		read(a); read(b);

		int x = find(a), y = find(b);

		if(x == y) continue;

		int fa = Merge(x, y);

		f[x] = f[y] = fa;

	}

	read(q);

	for(register int i = 1; i <= q; i++) {

		char c = getchar();

		while(c != 'Q' && c != 'B') c = getchar();

		if(c == 'Q') {

			int a, b;

			read(a); read(b);

			int x = find(a);

			if(root[x] -> size - 1 < b) {

				printf("-1\n");

				continue;

			}

			printf("%d\n", pre[find(root[x], b)]);

		} else {

			int a, b;

			read(a); read(b);

			int x = find(a), y = find(b);

			if(x == y) continue;

			int fa = Merge(x, y);

			f[x] = f[y] = fa;

		}

	}

	return 0;

}

巴特西

luoguP3224 [HNOI2012]永无乡

最新文章

热门文章