BZOJ3786 星系探索

写了发假的 \(\text{ETT}\)，\(\text{FQH-Treap}\) 维护括号序

\(\text{Code}\)

#include <bits/stdc++.h>
#define IN inline
#define eb emplace_back
using namespace std;

template <typename Tp>
IN void read(Tp &x) {
	x = 0; char ch = getchar(); int f = 0;
	for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar());
	for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
	if (f) x = ~x + 1;
}

typedef long long LL;
const int N = 2e5 + 5;
int n, m, a[N];
vector<int> G[N];
mt19937 Rnd(time(0));

struct ETT {
	int rt, size, st[N], ed[N], fa[N], rnd[N], ls[N], rs[N], sz[N], cf[N], cfs[N];
	LL sum[N], val[N], tag[N];
	
	IN int NewNode(int x, int y) {
		int p = ++size;
		sz[p] = 1, val[p] = sum[p] = x, cf[p] = cfs[p] = y, rnd[p] = Rnd();
		return p;
	}
	IN void pushup(int p) {
		sz[p] = sz[ls[p]] + sz[rs[p]] + 1,
		sum[p] = sum[ls[p]] + sum[rs[p]] + val[p],
		cfs[p] = cfs[ls[p]] + cfs[rs[p]] + cf[p];
	}
	IN void pushtag(int p, LL v){tag[p] += v, sum[p] += v * cfs[p], val[p] += v * cf[p];}
	IN void pushdown(int p) {
		(ls[p] && (pushtag(ls[p], tag[p]), 0)), (rs[p] && (pushtag(rs[p], tag[p]), 0)), tag[p] = 0;
	}
	IN int rank(int p) {
		int bz = 1, res = 0;
		while (p) (bz && (res += sz[ls[p]] + 1)), bz = (rs[fa[p]] == p), p = fa[p];
		return res;
	}
	
	void split(int p, int k, int &x, int &y) {
		fa[p] = 0;
		if (!p) return x = y = 0, void();
		pushdown(p);
		if (k <= sz[ls[p]]) y = p, split(ls[p], k, x, ls[y]), fa[ls[y]] = y;
		else x = p, split(rs[p], k - sz[ls[p]] - 1, rs[x], y), fa[rs[x]] = x;
		pushup(p);
	}
	int merge(int x, int y) {
		if (!x || !y) return x | y;
		if (rnd[x] < rnd[y]) return pushdown(x), rs[x] = merge(rs[x], y), fa[rs[x]] = x, pushup(x), x;
		return pushdown(y), ls[y] = merge(x, ls[y]), fa[ls[y]] = y, pushup(y), y;
	}
	
	IN void Modify(int x, int v) {
		int a, b, c;
		split(rt, rank(st[x]) - 1, a, b), split(b, rank(ed[x]) - rank(st[x]) + 1, b, c);
		pushtag(b, v), rt = merge(merge(a, b), c);
	}
	IN LL Query(int x) {
		int a, b; split(rt, rank(st[x]), a, b); LL res = sum[a]; return rt = merge(a, b), res;
	}
	IN void ChangeFa(int x, int y) {
		int a, b, c;
		split(rt, rank(st[x]) - 1, a, b), split(b, rank(ed[x]) - rank(st[x]) + 1, b, c);
		a = merge(a, c), split(a, rank(st[y]), a, c), rt = merge(merge(a, b), c);
	}
	void build(int x) {
		rt = merge(rt, st[x] = NewNode(a[x], 1));
		for(auto v : G[x]) build(v);
		rt = merge(rt, ed[x] = NewNode(-a[x], -1));
	}
}T;

int main() {
	read(n);
	for(int i = 2, x; i <= n; i++) read(x), G[x].eb(i);
	for(int i = 1; i <= n; i++) read(a[i]);
	T.build(1), read(m);
	char ch;
	for(int x, y; m; --m) {
		ch = getchar();
		if (ch == 'Q') read(x), printf("%lld\n", T.Query(x));
		else if (ch == 'C') read(x), read(y), T.ChangeFa(x, y);
		else read(x), read(y), T.Modify(x, y);
	}
}