Luogu4211 LCA 题解 (如何用分块艹过树剖题)

题目传送门

本来这题应该是树链剖分+差分O(nlog^2n)写的.(约150行?)

但是我不会树链剖分.我只好拿分块来艹过这题(约60行)

先预处理出每个块内所有点对树上所有点的贡献,记录下来.

使用倍增预处理,O(1)求lca,做到询问时O(1)处理散块.

询问时把中间块答案加上,散块答案加上即可.

预处理复杂度O(nsqrt(n)),查询复杂度O(msqrt(n)),空间复杂度O(nsqrt(n))

然后就草过去了.

代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50050;
const int MAXB = 350;
const int MAXM = 200050;
const int P = 201314;
typedef long long lint;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
vector <int> e[MAXN];
int n, q, blnm, L[MAXB], blsz, R[MAXB], belong[MAXN], dep[MAXN], dfn[MAXN];
int st[MAXM][21], lg2[MAXM], bin[MAXN], query[MAXB][MAXN], idx;
void dfsRMQ(int u) {
	st[++idx][0] = dep[u];
	dfn[u] = idx; 
	for(int v, i = 0; i < e[u].size(); ++i) {
		dep[(v = e[u][i])] = dep[u] + 1;
		dfsRMQ(v);
		st[++idx][0] = dep[u];
	}
}
void LCAinit() {
	dfsRMQ(1);
	for(int i = 2; i <= (n << 1); ++i) lg2[i] = lg2[i>>1] + 1;
	for(int t = 1; t <= 17; ++t) 
		for(int i = 1; i <= (n << 1) - (1 << t); ++i)
			st[i][t] = min(st[i][t-1], st[i+(1<<(t-1))][t-1]);
}
int LCA(int x, int y) {
	x = dfn[x]; y = dfn[y];
	if(x > y) swap(x, y);
	int k = lg2[y-x+1];
	return min(st[x][k], st[y-(1<<k)+1][k]);
}
void dfs1(int u) {for(int i = 0; i < e[u].size(); ++i) dfs1(e[u][i]), bin[u] += bin[e[u][i]];}
void dfs2(int u, int d) {for(int i = 0; i < e[u].size(); ++i) dfs2(e[u][i], d+bin[u]); bin[u] += d;}
int main() {
	read(n); read(q); blsz = sqrt(n); dep[1] = 1;
	for(int x, i = 2; i <= n; ++i) read(x), e[x+1].push_back(i);
	for(int i = 1; i <= n; ++i) {
		belong[i] = i / blsz + 1;
		if(belong[i] - belong[i-1]) L[belong[i]] = i, R[belong[i-1]] = i-1;
	}
	R[belong[n]] = n; L[1] = 1;
	LCAinit(); blnm = belong[n];
	for(int i = 1; i <= blnm; ++i) {
		memset(bin, 0, sizeof bin);
		for(int j = L[i]; j <= R[i]; ++j) ++bin[j];
		dfs1(1); dfs2(1, 0);
		for(int j = 1; j <= n; ++j) query[i][j] = bin[j];
	}
	for(int l, r, z; q--; ) {
		read(l); read(r); read(z);
		++l; ++r; ++z;
		int bl = belong[l-1]+1, br = belong[r+1]-1; lint ans = 0;
		for(; belong[l] != bl && l <= r; ++l) ans += LCA(l, z);
		for(; belong[r] != br && l <= r; --r) ans += LCA(r, z);
		for(int i = bl; i <= br; ++i) ans += query[i][z];
		printf("%d\n", ans % P);
	}
}

你问我跑的快不快?那当然没有树剖快呀.

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00