首页 > 代码库 > [BZOJ 3626] [LNOI2014] LCA 【树链剖分 + 离线 + 差分询问】

[BZOJ 3626] [LNOI2014] LCA 【树链剖分 + 离线 + 差分询问】

2024-11-06 16:50:39   203人阅读

题目链接： BZOJ - 3626

 

题目分析

考虑这样的等价问题，如果我们把一个点 x 到 Root 的路径上每个点的权值赋为 1 ，其余点的权值为 0，那么从 LCA(x, y) 的 Depth 就是从 y 到 Root 的路径上的点权和。

这个方法是可以叠加的，这是非常有用的一点。如果我们把 [l, r] 的每个点到 Root 的路径上所有点的权值 +1，再求出从 c 到 Root 的路径点权和，即为 [l, r] 中所有点与 c 的 LCA 的 Depth 和。

不仅满足可加性，还满足可减性，这就更好了！

那么我们就可以对每个询问 [l, r] 做一个差分，用 Query(r) - Query(l - 1) 作为答案。这样就有一种离线算法：将 n 个点依次操作，将其到 Root 的路径上的点权值 +1 ，然后如果这个点是某个询问的 l - 1 或 r ，就用那个询问的 c 求一下到 Root 的路径和，算入答案中。

Done！ 

写代码的时候忘记 % Mod 真是弱...

 

代码

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <queue>#include <vector>using namespace std;const int MaxN = 50000 + 5, Mod = 201314;int n, m, Index;int Father[MaxN], Depth[MaxN], Size[MaxN], Son[MaxN], Top[MaxN], Pos[MaxN];int T[MaxN * 4], D[MaxN * 4], Len[MaxN * 4], Ans[MaxN], Q[MaxN];vector<int> BA[MaxN], EA[MaxN];struct Edge {	int v;	Edge *Next;} E[MaxN], *P = E, *Point[MaxN];inline void AddEdge(int x, int y) {	++P; P -> v = y;	P -> Next = Point[x]; Point[x] = P;}int DFS_1(int x, int Dep) {	Depth[x] = Dep;	Size[x] = 1;	int SonSize, MaxSonSize;	SonSize = MaxSonSize = 1;	for (Edge *j = Point[x]; j; j = j -> Next) {		SonSize = DFS_1(j -> v, Dep + 1);		if (SonSize > MaxSonSize) {			MaxSonSize = SonSize;			Son[x] = j -> v;		}		Size[x] += SonSize;	}	return Size[x];}void DFS_2(int x) {	if (x == Son[Father[x]]) Top[x] = Top[Father[x]];	else Top[x] = x;	Pos[x] = ++Index;	if (Son[x] != 0) DFS_2(Son[x]);	for (Edge *j = Point[x]; j; j = j -> Next) 		if (j -> v != Son[x]) DFS_2(j -> v);}void Build_Tree(int x, int s, int t) {	Len[x] = t - s + 1;	D[x] = T[x] = 0;	if (s == t) return;	int m = (s + t) >> 1;	Build_Tree(x << 1, s, m);	Build_Tree(x << 1 | 1, m + 1, t);}inline void Update(int x) {	T[x] = T[x << 1] + T[x << 1 | 1];	T[x] %= Mod;}inline void Paint(int x, int Num) {	T[x] += Num * Len[x];	T[x] %= Mod;	D[x] += Num;	D[x] %= Mod;}inline void PushDown(int x) {	if (D[x] == 0) return;	Paint(x << 1, D[x]);	Paint(x << 1 | 1, D[x]);	D[x] = 0;}void Add(int x, int s, int t, int l, int r) {	if (l <= s && r >= t) {		Paint(x, 1);		return;	}	PushDown(x);	int m = (s + t) >> 1;	if (l <= m) Add(x << 1, s, m, l, r);	if (r >= m + 1) Add(x << 1 | 1, m + 1, t, l, r);	Update(x);}void EAdd(int x) {	int fx;	fx = Top[x];	while (fx != 1) {		Add(1, 1, n, Pos[fx], Pos[x]);		x = Father[fx];		fx = Top[x];	}	Add(1, 1, n, Pos[1], Pos[x]);}int Get(int x, int s, int t, int l, int r) {	if (l <= s && r >= t) return T[x];	int ret = 0;	PushDown(x);	int m = (s + t) >> 1;	if (l <= m) ret += Get(x << 1, s, m, l, r);	if (r >= m + 1) ret += Get(x << 1 | 1, m + 1, t, l, r);	return ret % Mod;}int EGet(int x) {	int ret = 0, fx;	fx = Top[x];	while (fx != 1) {		ret += Get(1, 1, n, Pos[fx], Pos[x]);		ret %= Mod;		x = Father[fx];		fx = Top[x];	}	ret += Get(1, 1, n, Pos[1], Pos[x]);	return ret % Mod;}int main() {	scanf("%d%d", &n, &m);	int a, b, c;	for (int i = 2; i <= n; ++i) {		scanf("%d", &a);		++a;		Father[i] = a;		AddEdge(a, i);	}	DFS_1(1, 1);	Index = 0;	DFS_2(1);	Build_Tree(1, 1, n);	for (int i = 1; i <= m; ++i) {		scanf("%d%d%d", &a, &b, &c);		++a; ++b; ++c;		Q[i] = c;		BA[a - 1].push_back(i);		EA[b].push_back(i);	}	for (int i = 1; i <= n; ++i) {		EAdd(i);		for (int j = 0; j < BA[i].size(); ++j) 			Ans[BA[i][j]] -= EGet(Q[BA[i][j]]);		for (int j = 0; j < EA[i].size(); ++j) 			Ans[EA[i][j]] += EGet(Q[EA[i][j]]);	}	for (int i = 1; i <= m; ++i) printf("%d\n", (Ans[i] + Mod) % Mod);	return 0;}

　　

[BZOJ 3626] [LNOI2014] LCA 【树链剖分 + 离线 + 差分询问】


联系
我们