bzoj2959: 长跑(LCT+并查集)

题解

动态树Link-cut tree(LCT)总结

LCT常数大得真实

没有环,就是\(lct\)裸题吧

有环,我们就可以绕环转一圈,缩点

怎么搞?

当形成环时,把所有点的值全部加到一个点上,用并查集维护加到哪个点上

判断连通性再用一个并查集

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

	x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

	x = f ? -x : x;

	return ;

}

template<class T> inline void write(T x) {

	if (!x) {putchar(48);return ;}

	if (x < 0) x = -x, putchar('-');

	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int N = 150010;

struct node {

	int v, s, fa, ch[2];

	bool rev;

}t[N];

int S[N], top;

#define lson (t[x].ch[0])

#define rson (t[x].ch[1])

void pushup(int x) {t[x].s = (t[lson].s + t[rson].s + t[x].v);return ;}

void putrev(int x) {

	swap(lson, rson);

	t[x].rev ^= 1;

	return ;

}

void pushdown(int x) {

	if (t[x].rev) {

		if (lson) putrev(lson);

		if (rson) putrev(rson);

		t[x].rev = 0;

	}

}

int fa[N], Fa[N];

int find(int x) {

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

}

int Find(int x) {

	return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);

}

bool isroot(int x) {

	return (t[find(t[x].fa)].ch[0] != x) && (t[find(t[x].fa)].ch[1] != x);

}

void rotate(int x) {

	int y = find(t[x].fa), z = find(t[y].fa), k = t[y].ch[1] == x;

	if (!isroot(y)) t[z].ch[t[z].ch[1] == y] = x;

	t[x].fa = z;

	t[t[x].ch[k^1]].fa = y, t[y].ch[k] = t[x].ch[k^1];

	t[x].ch[k^1] = y; t[y].fa = x;

	pushup(y);

	return ;

}

void splay(int x) {

	S[top = 1] = x;

	for (RG int i = x; !isroot(i); i = find(t[i].fa)) S[++top] = find(t[i].fa);

	for (RG int i = top; i; i--) pushdown(S[i]);

	while (!isroot(x)) {

		int y = find(t[x].fa), z = find(t[y].fa);

		if (!isroot(y))

			(t[y].ch[1] == x) ^ (t[z].ch[1] == y) ? rotate(x) : rotate(y);

		rotate(x);

	}

	pushup(x);

	return ;

}

void access(int x) {

	for (int y = 0; x; y = x, x = find(t[x].fa))

		splay(x), t[x].ch[1] = y, pushup(x);

}

void makeroot(int x) {

	access(x); splay(x); putrev(x);

	return ;

}

void link(int x, int y) {

	makeroot(x);

	t[x].fa = y;

}

void split(int x, int y) {

	makeroot(x), access(y), splay(y);

	return ;

}

int a[N], n, m;

void dfs(int x, int y) {

	fa[x] = y;

	pushdown(x);

	if (lson) dfs(lson, y);

	if (rson) dfs(rson, y);

	return ;

}

int main() {

	read(n), read(m);

	for (int i = 1; i <= n; i++) read(a[i]), fa[i] = Fa[i] = i, t[i].s = t[i].v = a[i];

	while (m--) {

		int x, y, op;

		read(op), read(x), read(y);

		if (op == 1) {

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

			if (x == y) continue;

			if (Find(x) != Find(y)) {

				link(x, y);

				Fa[Find(y)] = Find(x);

			}

			else {

				split(x, y);

				t[y].v = t[y].s;

				dfs(y, y);

				t[y].ch[0] = 0;

			}

		}

		else if (op == 2) {

			int tx = find(x);

			splay(tx);

			t[tx].s += y - a[x];

			t[tx].v += y - a[x];

			a[x] = y;

		}

		else {

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

			if (Find(x) != Find(y)) {

				puts("-1");

				continue;

			}

			split(x, y);

			printf("%d\n", t[y].s);

		}

	}

	return 0;

}

巴特西

bzoj2959: 长跑(LCT+并查集)

题解

Code

最新文章

热门文章