P3384 【模板】重链剖分/树链剖分

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;

const int M = 200005;
const int N = 100005;
int son[N], dep[N], siz[N], top[N], fa[N], id[N];
int n, m, r, p, cnt = 1, head[N];
int newcnt, tmp[N], w[N];
int t[N << 2], lazy[N << 2];

inline int rd() {
	int x = 0, w = 1;
	char c = getchar();
	while (c < 48 || c > 57) {
		if (c == 45) w *= -1;
		c = getchar();
	}
	while (c >= 48 && c <= 57) {
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}
	return x * w;
}

struct node {
	int to, next, w;
} e[M];

void addi(int u, int v) {
	e[++cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void add(int u, int v) {
	addi(u, v);
	addi(v, u);
}

void dfs1(int x, int faa, int depth) {
	siz[x] = 1;
	fa[x] = faa;
	dep[x] = depth;
	int mmax = -1;
	for (int i = head[x]; i; i = e[i].next) {
		int v = e[i].to;
		if (v == faa) continue;
		dfs1(v, x, depth + 1);
		siz[x] += siz[v];
		if (siz[v] > mmax) {
			son[x] = v;
			mmax = siz[v];
		}
	}
}

void dfs2(int x, int topf) {
	id[x] = ++newcnt;
	w[newcnt] = tmp[x];
	top[x] = topf;
	if (son[x]) dfs2(son[x], topf);
	for (int i = head[x]; i; i = e[i].next) {
		int v = e[i].to;
		if (v == fa[x] || v == son[x]) continue;
		dfs2(v, v);
	}
}

void pushup(int rt) {
	t[rt] = t[rt << 1] + t[rt << 1 | 1];
}

void pushdown(int rt, int l, int r) {
	if(lazy[rt]) {
		int len = r - l + 1;
		t[rt << 1] += lazy[rt] * (len - (len >> 1));
		t[rt << 1 | 1] += lazy[rt] * (len >> 1);
		t[rt << 1] %= p;
		t[rt << 1 | 1] %= p;
		lazy[rt << 1] += lazy[rt];
		lazy[rt << 1 | 1] += lazy[rt];
		lazy[rt] = 0;
	}
}

inline void build(int rt, int l ,int r){
	if(l == r) {
		t[rt] = w[l];
		t[rt] %= p;
		return;
	}
	int mid = (l + r) >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt);
}

inline int query(int x, int y, int l, int r, int rt) {
	if(x <= l && r <= y) {
		return t[rt] % p;
	}
	pushdown(rt, l, r);
	int mid = (l + r) >> 1;
	int ans = 0;
	if(x <= mid) ans += query(x, y, l, mid, rt << 1);
	if(y >  mid) ans += query(x, y, mid + 1, r, rt << 1 | 1); 
	pushup(rt);
	return ans % p;
}

inline void update(int x, int y, int l, int r, int rt, int k) {
	if(x <= l && r <= y) {
		t[rt] += k * (r - l + 1);
		t[rt] %= p;
		lazy[rt] += k;
		return;
	}
	pushdown(rt, l, r);
	int mid = (l + r) >> 1;
	if(x <= mid) update(x, y, l, mid, rt << 1, k);
	if(y >  mid) update(x, y, mid + 1, r, rt << 1 | 1, k); 
	pushup(rt);
}

inline void updaterange(int x, int y, int k) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])swap(x, y);
		update(id[top[x]], id[x], 1, n, 1, k);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])swap(x, y);
	update(id[x], id[y], 1, n, 1, k);
}

inline int queryrange(int x, int y) {
	int ans = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])swap(x, y);
		ans += query(id[top[x]], id[x], 1, n ,1);
		ans %= p;
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])swap(x, y);
	ans += query(id[x], id[y], 1, n, 1);
	return ans % p;
}

signed main() {
	n = rd(), m = rd(), r = rd(), p = rd();
	for (int i = 1; i <= n; i++) {
		tmp[i] = rd();
	}
	for (int i = 1; i <= n - 1; i++) {
		int u = rd(), v = rd();
		add(u, v);
	}
	dfs1(r, r, 1);
	dfs2(r, r);
	build(1, 1, n);
	while (m --) {
		int f = rd();
		if (f == 1) {
			int x = rd(), y = rd(), z = rd();
			updaterange(x, y, z);
		}
		if (f == 2) {
			int x = rd(), y = rd();
			printf("%lld\n", queryrange(x, y)% p) ;
		}
		if (f == 3) {
			int x = rd(), y = rd();
			update(id[x], id[x] + siz[x] - 1, 1, n, 1, y);
		}
		if (f == 4) {
			int x = rd();
			printf("%lld\n", query(id[x], id[x] + siz[x] - 1, 1, n, 1) % p);
		}
	}
	return 0;
}

终于过了呜呜呜。

痛苦log：

• 发现query函数没有返回值 RE
• 发现build函数中错写m+1，应为mid+1
• 发现update函数if里面没有return
• 发现pushdown函数的len写法不对
• 数组小了炸了
• ACCCCCCCCCCC！！！！！！！！！