bzoj3123 [Sdoi2013]森林树上主席树+启发式合并

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=3123

题解

如果是静态的查询操作，那么就是直接树上主席树的板子。

但是我们现在有了一个连接两棵树的操作。

那么我们就采取启发式合并的方法来暴力重新建主席树。

对于表示树上前缀和的主席树来说，连接两条边以后，会影响到的点只有其中的一棵树。

所以不妨把较小的那一棵树暴力重新建立主席树。

另外由于树形态不固定，所以要用倍增 lca。

时间复杂度 \(O(n\log^2n)\)，空间复杂度 \(O(q\log^n)\)。（也许垃圾节点回收可以做做到一个 \(log\) ？）

输入的第一个数据不是数据组数！！！被坑了好久。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 8e4 + 7;

const int LOG = 18;

int n, m, Q, nod, dis, la;

int a[N], b[N], f[N][LOG], dep[N], siz[N], fa[N], rt[N];

struct Edge { int to, ne; } g[N << 1]; int head[N], tot;

inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }

inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

struct Node { int lc, rc, val; } t[N * 16 * 16];

inline void ins(int &o, int p, int L, int R, int x) {

//	dbg("o = %d, p = %d, L = %d, R = %d, x = %d\n", o, p, L, R, x);

	t[o = ++nod] = t[p], ++t[o].val;

	if (L == R) return;

	int M = (L + R) >> 1;

	if (x <= M) ins(t[o].lc, t[p].lc, L, M, x);

	else ins(t[o].rc, t[p].rc, M + 1, R, x);

}

inline int qval(int o1, int o2, int p1, int p2, int L, int R, int k) {

//	dbg("o1 = %d, o2 = %d, p1 = %d, p2 = %d, L = %d, R = %d, k = %d, t[o1].val = %d, t[o2].val = %d, t[p1].val = %d, t[p2].val = %d\n", o1, o2, p1, p2, L, R, k, t[o1].val, t[o2].val, t[p1].val, t[p2].val);

	if (L == R) return L;

	int M = (L + R) >> 1, ls = t[t[o1].lc].val + t[t[o2].lc].val - t[t[p1].lc].val - t[t[p2].lc].val;

	if (k <= ls) return qval(t[o1].lc, t[o2].lc, t[p1].lc, t[p2].lc, L, M, k);

	else return qval(t[o1].rc, t[o2].rc, t[p1].rc, t[p2].rc, M + 1, R, k - ls);

}

inline void dfs(int x, int rt, int fa = 0) {

//	dbg("x = %d, rt = %d, fa = %d\n", x, rt, fa);

	dep[x] = dep[fa] + 1, f[x][0] = fa, siz[x] = 1;

	ins(::rt[x], ::rt[fa], 1, dis, a[x]);

	if (rt) ::fa[x] = rt;

	for (int i = 1; i < LOG; ++i) f[x][i] = f[f[x][i - 1]][i - 1];

	for fec(i, x, y) if (y != fa) dfs(y, rt, x), siz[x] += siz[y];

}

inline int lca(int x, int y) {

	if (dep[x] < dep[y]) std::swap(x, y);

	for (int i = LOG - 1; ~i; --i) if (dep[f[x][i]] >= dep[y]) x = f[x][i];

	if (x == y) return x;

	for (int i = LOG - 1; ~i; --i) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];

	return f[x][0];

}

inline void lsh() {

	std::sort(b + 1, b + n + 1);

	dis = std::unique(b + 1, b + n + 1) - b - 1;

	for (int i = 1; i <= n; ++i) a[i] = std::lower_bound(b + 1, b + dis + 1,  a[i]) - b;

}

inline void work() {

	lsh();

	for (int i = 1; i <= n; ++i) if (!dep[i]) dfs(i, i);

//	dbg("***********\n");

	while (Q--) {

		char opt[5];

		scanf("%s", opt);

		if (*opt == 'Q') {

			int x, y, k, p;

			read(x), read(y), read(k);

			x ^= la, y ^= la, k ^= la;

			p = lca(x, y);

//			dbg("x = %d, y = %d, k = %d, p = %d, la = %d\n", x, y, k, p, la);

			printf("%d\n", la = b[qval(rt[x], rt[y], rt[p], rt[f[p][0]], 1, dis, k)]);

		} else {

			int x, y, fx, fy;

			read(x), read(y);

			x ^= la, y ^= la;

			fx = find(x), fy = find(y);

//			dbg("siz[fx] = %d, siz[fy] = %d\n", siz[fx], siz[fy]);

			if (siz[fx] > siz[fy]) {

				fa[fy] = fx, siz[fx] += siz[fy];

				dfs(y, 0, x), adde(x, y);

			} else {

				fa[fx] = fy, siz[fy] += siz[fx];

				dfs(x, 0, y), adde(x, y);

			}

		}

	}

}

inline void init() {

	read(n), read(m), read(Q);

	for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i];

	int x, y;

	for (int i = 1; i <= m; ++i) read(x), read(y), adde(x, y);

}

int main() {

#ifdef hzhkk

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

#endif

	read(n);

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj3123 [Sdoi2013]森林树上主席树+启发式合并

题目传送门

题解

最新文章

热门文章

巴特西

bzoj3123 [Sdoi2013]森林 树上主席树+启发式合并

题目传送门

题解

最新文章

热门文章

bzoj3123 [Sdoi2013]森林树上主席树+启发式合并