bzoj3091 城市旅行 LCT + 区间合并

题目传送门

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

题解

调了整个晚自习才调出来的问题。

乍一看是个 LCT 板子题。

再看一眼还是个 LCT 板子题，不过需要考虑两个区间的结果的合并。

首先考虑到期望可以转化为每一个区间的权值和。那么对于每一个区间，我们维护一个 $s, ls, rs, sum$ 分别表示整个区间的和，所有前缀的和，所有后缀的和，整个区间的子区间权值和。

那么在区间合并的时候，$rs$ 会被计算右区间大小次，$ls$ 会被计算左区间大小次，直接合并就可以了。

合并出 $ls, rs$ 的时候考虑每一个区间的值的变化即可。

还有一个东西是加标记 $k$ 对一个区间的影响。设区间长度为 $len$。

这个标记对 $ls, rs$ 的影响很显然，就是每一个前缀的长度和 $\cdot k$，即 $\frac{len(len+1)k}2 $。

对于 $sum$ 的影响是所有子区间长度之和。可以从每一个长度的区间数量来求，过程中式子比较繁琐，只给出答案：$\frac{len(len+1)(len+2)k}6$。

注意：

$ls, rs, sum$ 一类东西太多，不要搞混；
不连通时不要操作！！！不连通时不要操作！！！不连通时不要操作！！！

时间复杂度 $O(m\log n)$。

#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 = 50000 + 7;

#define lc c[0]

#define rc c[1]

int n, m;

int a[N];

struct Node {

	int c[2], fa, rev, sz, v, add;

	ll s, sum, ls, rs;

} t[N];

int st[N];

inline bool isroot(int o) { return t[t[o].fa].lc != o && t[t[o].fa].rc != o; }

inline bool idtfy(int o) { return t[t[o].fa].rc == o; }

inline void connect(int fa, int o, int d) { t[fa].c[d] = o, t[o].fa = fa; }

inline Node add_tag(Node a, int k) {

	a.v += k, a.add += k;

	a.s += (ll)k * a.sz;

	a.sum += (ll)a.sz * (a.sz + 1) * (a.sz + 2) / 6 * k;

	a.ls += (ll)a.sz * (a.sz + 1) / 2 * k;

	a.rs += (ll)a.sz * (a.sz + 1) / 2 * k;

	return a;

}

inline void pushup(int o) {

	assert(!t[o].rev && !t[o].add);

	const Node &tl = t[t[o].lc], &tr = t[t[o].rc];

	t[o].sz = tl.sz + tr.sz + 1;

	t[o].s = tl.s + tr.s + t[o].v;

	t[o].ls = tl.ls + (tl.s + t[o].v) * (tr.sz + 1) + tr.ls;

	t[o].rs = tr.rs + (tr.s + t[o].v) * (tl.sz + 1) + tl.rs;

	t[o].sum = tl.sum + tr.sum + (ll)t[o].v * (tl.sz + 1) * (tr.sz + 1) + tl.rs * (tr.sz + 1) + tr.ls * (tl.sz + 1);

}

inline void pushdown(int o) {

	if (t[o].rev) {

		if (t[o].lc) t[t[o].lc].rev ^= 1, std::swap(t[t[o].lc].lc, t[t[o].lc].rc), std::swap(t[t[o].lc].ls, t[t[o].lc].rs);

		if (t[o].rc) t[t[o].rc].rev ^= 1, std::swap(t[t[o].rc].lc, t[t[o].rc].rc), std::swap(t[t[o].rc].ls, t[t[o].rc].rs);

		t[o].rev = 0;

	}

	if (t[o].add) {

		if (t[o].lc) t[t[o].lc] = add_tag(t[t[o].lc], t[o].add);

		if (t[o].rc) t[t[o].rc] = add_tag(t[t[o].rc], t[o].add);

		t[o].add = 0;

	}

}

inline void rotate(int o) {

	int fa = t[o].fa, pa = t[fa].fa, d1 = idtfy(o), d2 = idtfy(fa), b = t[o].c[d1 ^ 1];

	if (!isroot(fa)) t[pa].c[d2] = o; t[o].fa = pa;

	connect(o, fa, d1 ^ 1), connect(fa, b, d1);

	pushup(fa), pushup(o);

}

inline void splay(int o) {

	int x = o, tp = 0;

	st[++tp] = x;

	while (!isroot(x)) st[++tp] = x = t[x].fa;

	while (tp) pushdown(st[tp--]);

	while (!isroot(o)) {

		int fa = t[o].fa;

		if (isroot(fa)) rotate(o);

		else if (idtfy(o) == idtfy(fa)) rotate(fa), rotate(o);

		else rotate(o), rotate(o);

	}

}

inline void access(int o) {

	for (int x = 0; o; o = t[x = o].fa)

		splay(o), t[o].rc = x, pushup(o);

}

inline void mkrt(int o) {

	access(o), splay(o);

	t[o].rev ^= 1, std::swap(t[o].lc, t[o].rc), std::swap(t[o].ls, t[o].rs);

}

inline int getrt(int o) {

	access(o), splay(o);

	while (pushdown(o), t[o].lc) o = t[o].lc;

	return splay(o), o;

}

inline void link(int x, int y) {

	mkrt(x);

	if (getrt(y) != x) t[x].fa = y;

}

inline void cut(int x, int y) {

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

	if (t[y].lc == x && !t[x].rc) t[y].lc = t[x].fa = 0, pushup(y);

}

inline void work() {

	while (m--) {

		int opt, x, y, d;

		read(opt), read(x), read(y);

		if (opt == 1) cut(x, y);

		else if (opt == 2) link(x, y);

		else if (opt == 3) read(d), getrt(x) == getrt(y) && (mkrt(x), access(y), splay(y), t[y] = add_tag(t[y], d), 1);

		else if (getrt(x) != getrt(y)) puts("-1");

		else {

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

			ll sum = t[y].sum, cnt = (ll)t[y].sz * (t[y].sz + 1) / 2, p = std::__gcd(sum, cnt);

			printf("%lld/%lld\n", sum / p, cnt / p);

		}

	}

}

inline void init() {

	read(n), read(m);

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

	for (int i = 1; i <= n; ++i) t[i].v = a[i], pushup(i);

	int x, y;

	for (int i = 1; i < n; ++i) read(x), read(y), link(x, y);

}

int main() {

#ifdef hzhkk

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

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj3091 城市旅行 LCT + 区间合并

题目传送门

题解

最新文章

热门文章