[HNOI2015]开店简要题解

主席树。

推下式子，发现点的深度和好算，lca深度和不好算。

lca深度之和有个套路：先给a到根路径+1，再算b到根的和。

如果可以离线，即LNOI的LCA。本题强制在线，可持久化。

由于区间修改，使用标记永久化。

注意修改要复制全，关于和的修改有些细节：

int xiugai(int i, int j, int l, int r, int L, int R) {

	if (R <= l || r <= L) return i;

	int rt = ++sl;

	cl[rt] = cl[i];	cr[rt] = cr[i];

	he[rt] = he[i];	ld[rt] = ld[i];

	if (L <= l && r <= R) {

		he[rt] += su[j];

		ld[rt] = ld[i] + 1;

		return rt;

	}

	int m = (l + r) >> 1;

	he[rt] -= (he[cl[rt]] + he[cr[rt]]);

	cl[rt] = xiugai(cl[rt], j << 1, l, m, L, R);

	cr[rt] = xiugai(cr[rt], (j << 1) | 1, m, r, L, R);

	he[rt] += (he[cl[rt]] + he[cr[rt]]);

	return rt;

}

正常空间需要4倍mlogn：修改区间拆分2倍，上传2倍。应该跑不满。

然而本题是树剖，跑不满，所以开到\(2.5*10^7\)就行。

代码：

#include <stdio.h>

#include <stdlib.h>

#define M 20000010

#define ll long long

#define re register

inline int max(int a, int b) {

	return a > b ? a: b;

}

inline int min(int a, int b) {

	return a < b ? a: b;

}

inline int read() {

	re char ch;

	while ((ch = getchar()) == '\n' || ch == ' ' || ch == '\r');

	re int jg = ch - '0';

	while ((ch = getchar()) >= '0' && ch <= '9') jg = (jg << 3) + (jg << 1) + ch - '0';

	return jg;

}

int fr[150010],ne[300010],v[300010],w[300010],bs = 0;

void addb(int a, int b, int c) {

	v[bs] = b;

	w[bs] = c;

	ne[bs] = fr[a];

	fr[a] = bs++;

}

int fa[150010],son[150010],sd[150010],cd[150010],jl[150010];

int dfs1(int u, int f) {

	fa[u] = f;

	sd[u] = sd[f] + 1;

	jl[u] = jl[f] + cd[u];

	int ma = -1,he = 1;

	son[u] = -1;

	for (int i = fr[u]; i != -1; i = ne[i]) {

		if (v[i] == f) continue;

		cd[v[i]] = w[i];

		int rt = dfs1(v[i], u);

		he += rt;

		if (rt > ma) {

			ma = rt;

			son[u] = v[i];

		}

	}

	return he;

}

int top[150010],bh[150010],tm = 0;

void dfs2(int u, int f, int tp) {

	top[u] = tp;

	bh[u] = ++tm;

	if (son[u] == -1) return;

	dfs2(son[u], u, tp);

	for (int i = fr[u]; i != -1; i = ne[i]) {

		if (v[i] != f && v[i] != son[u]) dfs2(v[i], u, v[i]);

	}

}

int js[150010],cl[M],cr[M],ld[M],sl = 0,su[600010];

ll he[M],jh[150010];

void jianshu(int i, int l, int r) {

	if (l + 1 == r) {

		su[i] = js[l];

		return;

	}

	int m = (l + r) >> 1;

	jianshu(i << 1, l, m);

	jianshu((i << 1) | 1, m, r);

	su[i] = su[i << 1] + su[(i << 1) | 1];

}

int jianshu(int l, int r) {

	int rt = ++sl;

	he[rt] = ld[rt] = 0;

	if (l + 1 == r) return rt;

	int m = (l + r) >> 1;

	cl[rt] = jianshu(l, m);

	cr[rt] = jianshu(m, r);

	return rt;

}

int build(int n) {

	for (int i = 1; i <= n; i++) js[bh[i]] = cd[i];

	jianshu(1, 1, n + 1);

	return jianshu(1, n + 1);

}

int xiugai(int i, int j, int l, int r, int L, int R) {

	if (R <= l || r <= L) return i;

	int rt = ++sl;

	cl[rt] = cl[i];	cr[rt] = cr[i];

	he[rt] = he[i];	ld[rt] = ld[i];

	if (L <= l && r <= R) {

		he[rt] += su[j];

		ld[rt] = ld[i] + 1;

		return rt;

	}

	int m = (l + r) >> 1;

	he[rt] -= (he[cl[rt]] + he[cr[rt]]);

	cl[rt] = xiugai(cl[rt], j << 1, l, m, L, R);

	cr[rt] = xiugai(cr[rt], (j << 1) | 1, m, r, L, R);

	he[rt] += (he[cl[rt]] + he[cr[rt]]);

	return rt;

}

ll getsum(int i, int j, int l, int r, int L, int R, int lh) {

	if (R <= l || r <= L) return 0;

	if (L <= l && r <= R) return 1ll * lh * su[j] + he[i];

	int m = (l + r) >> 1;

	return getsum(cl[i], j << 1, l, m, L, R, lh + ld[i]) + getsum(cr[i], (j << 1) | 1, m, r, L, R, lh + ld[i]);

}

int xiugai(int od, int x, int n) {

	while (x != 0) {

		od = xiugai(od, 1, 1, n + 1, bh[top[x]], bh[x] + 1);

		x = fa[top[x]];

	}

	return od;

}

ll getsum(int ro, int x, int n) {

	ll jg = 0;

	while (x != 0) {

		jg += getsum(ro, 1, 1, n + 1, bh[top[x]], bh[x] + 1, 0);

		x = fa[top[x]];

	}

	return jg;

}

struct SPx {

	int z,	i;

};

SPx px[150010];

int cmp(const void * a, const void * b) {

	return ((SPx * ) a) ->z - ((SPx * ) b) ->z;

}

int find(int n, int x) {

	int l = 0,	r = n;

	while (l < r) {

		int m = (l + r + 1) >> 1;

		if (px[m].z <= x) l = m;

		else r = m - 1;

	}

	return l;

}

int gen[150010];

ll getans(int L, int R, int u, int n) {

	int r = find(n, R);

	int l = find(n, L - 1);

	ll lc = getsum(gen[r], u, n) - getsum(gen[l], u, n);

	ll jg = 1ll * (r - l) * jl[u] + (jh[r] - jh[l]) - lc * 2;

	return jg;

}

void insert(int i, int n) {

	gen[i] = xiugai(gen[i - 1], px[i].i, n);

	jh[i] = jh[i - 1] + jl[px[i].i];

}

int main() {

	int n,	q,	m;

	ll la = 0;

	scanf("%d%d%d", &n, &q, &m);

	for (int i = 1; i <= n; i++) {

		fr[i] = -1;

		px[i].i = i;

		px[i].z = read();

	}

	qsort(px + 1, n, sizeof(SPx), cmp);

	for (int i = 0; i < n - 1; i++) {

		int a,		b,		c;

		a = read();

		b = read();

		c = read();

		addb(a, b, c);

		addb(b, a, c);

	}

	dfs1(1, 0);

	dfs2(1, 0, 1);

	gen[0] = build(n);

	for (int i = 1; i <= n; i++) insert(i, n);

	for (int i = 0; i < q; i++) {

		int u,		a,		b;

		u = read();

		a = read();

		b = read();

		int L = min((a + la) % m, (b + la) % m);

		int R = max((a + la) % m, (b + la) % m);

		la = getans(L, R, u, n);

		printf("%lld\n", la);

	}

	return 0;

}

巴特西

[HNOI2015]开店简要题解

最新文章

热门文章

巴特西

[HNOI2015]开店 简要题解

最新文章

热门文章

[HNOI2015]开店简要题解