P4211 [LNOI2014]LCA

首先贡献变成前缀的差,即 $[1,l-1]$ 和 $[1,r]$

然后考虑所有询问离线

按照一维的前缀信息排序

差分,深度等于 $dep_u-dep_f$ 求和,因此对于u加入,我们只需要对于u到根的路径加即可

观察不难得出询问点z相当于z到根路径的前缀求和

使用LCT实现即可,树剖也可以

调了两个小锅,第一个是我们pushdown的时候注意根也要pushdown...

第二个是我们l可能为0,此时我们内层循环不会工作

#include<bits/stdc++.h>
const int MAXN = 2e5 + 7;
const int P = 201314;
using namespace std;

int n, q, ccnt, tot;
int home[MAXN], nxt[MAXN], to[MAXN], ans[MAXN];

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

struct rec {
	int l, r, z;
	bool operator<(const rec &x)const {
		return l < x.l;
	}
} b[MAXN];

inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}

namespace LCT {
#define L (ch[x][0])
#define R (ch[x][1])
	int ch[MAXN][2], f[MAXN], st[MAXN], fz[MAXN], tag[MAXN], a[MAXN], sz[MAXN], sum[MAXN];
	inline bool nroot(int x) {
		return ch[f[x]][0] == x || ch[f[x]][1] == x;
	}
	inline void pushup(int x) {
		sz[x] = sz[L] + sz[R] + 1;
		sum[x] = 0;
		add(sum[x], sum[L]);
		add(sum[x], sum[R]);
		add(sum[x], a[x]);
	}
	inline void mdf(int k, int x) {
		tag[k] += x;
		add(sum[k], 1ll * x * sz[k] % P);
		a[k] += x;
	}
	inline void pushR(int x) {
		L ^= R ^= L ^= R;
		fz[x] ^= 1;
	}
	inline void pushdown(int x) {
		if(fz[x]) {
			if(L)pushR(L);
			if(R)pushR(R);
			fz[x] = 0;
		}
		if(tag[x]) {
			if(L)mdf(L, tag[x]);
			if(R)mdf(R, tag[x]);
			tag[x] = 0;
		}
	}
	inline void rotate(int x) {
		int y = f[x], z = f[y], k = ch[y][1] == x, w = ch[x][!k];
		if(nroot(y))ch[z][ch[z][1] == y] = x;
		ch[x][!k] = y;
		ch[y][k] = w;
		if(w)f[w] = y;
		f[y] = x;
		f[x] = z;
		pushup(y);
	}
	inline void outtree() {
		for(int x = 1; x <= n; ++x) {
			printf("u:%d L:%d R:%d F:%d %d %d %d %d\n", x, L, R, f[x], sum[x], a[x], sz[x], tag[x]);
		}
		puts("\n");
	}
	inline void splay(int x) {
		int y = x, z = 0;
		st[++z] = y;
		while(nroot(y)) {
			st[++z] = f[y];
			y = f[y];
		}
		while(z) {
			pushdown(st[z]);
			--z;
		}
		while(nroot(x)) {
			y = f[x], z = f[y];
			if(nroot(y))
				rotate((ch[y][1] == x) ^ (ch[z][1] == y) ? x : y);
			rotate(x);
		}
		pushup(x);
	}
	inline void access(int x) {
		for(int y = 0; x; x = f[y = x]) {
			splay(x);
			R = y;
			pushup(x);
		}
	}
	inline void makeroot(int x) {
		access(x);
		splay(x);
		pushR(x);
	}
	inline void split(int x, int y) {
		makeroot(x);
		access(y);
		splay(y);
	}
	inline void link(int x, int y) {
		f[y] = x;
	}

}
using namespace LCT;

int main() {
	scanf("%d%d", &n, &q);
	for(int i = 2; i <= n; ++i)scanf("%d", &f[i]), link(f[i] + 1, i);
	for(int i = 1, l, r, z; i <= q; ++i) {
		scanf("%d%d%d", &l, &r, &z);
		++l;
		++r;
		++z;
		b[++tot].l = l - 1;
		b[tot].z = z;
		b[tot].r = -i;
		b[++tot].l = r;
		b[tot].z = z;
		b[tot].r = i;
	}
	sort(b + 1, b + tot + 1);
	int j = 1;
	while(b[j].l == 0)++j;//有什么用??
	for(int i = 1; i <= n; ++i) {
		split(1, i);
		mdf(i, 1);
		for(; b[j].l == i && j <= tot; ++j) {
			split(1, b[j].z);
			if(b[j].r < 0) {
				b[j].r = -b[j].r;
				add(ans[b[j].r], P - sum[b[j].z]); //直接加就好了
			} else {
				add(ans[b[j].r], sum[b[j].z]);
			}
		}
	}
	for(int i = 1; i <= q; ++i)printf("%d\n", ans[i]);
	return 0;
}

本题也可以直接套用分块的做法,但是实在没必要qaq

夏晓光(loveJY)的博客

AT5202 [AGC038E] Gachapon