[BZOJ 3052] [wc2013] 糖果公园【树上莫队】

题目链接：BZOJ - 3052

题目分析

这道题就是非常经典的树上莫队了，并且是带修改的莫队。

带修改的莫队：将询问按照左端点所在的块编号为第一关键字，右端点所在的块为第二关键字，位于第几次修改之后为第三关键字排序。

我们将块的大小设置在 n^(2/3) ，这样一共有 n^(1/3) 个块。最后算法的总复杂度会是 n^(5/3) 。

每一次如何从上一个询问转移来呢？

假设上一个询问是 (lx, ly, lt) ，这次的询问是 (x, y, t) 。t 代表是在第 t 次修改操作之后。

首先先移动 t ，如果 t > lt ，那么就将 (lt+1, t) 的修改操作都做一次。如果 t < lt, 就从 t 开始撤销修改操作，一直撤销到 lt+1 。为了能够撤销修改操作，我们需要预处理每次修改操作修改的位置原来是什么颜色。

然后就是移动树上路径了，从 (lx, ly) 到 (x, y) 。这个有一个经典的做法。

我们用 S(a, b) 表示从 a 到 b 的路径上的所有点。我们不直接维护 S(x, y) 的路径上的点，而是维护一个 T(x, y)，即 S(x, y) 的路径上的点除去 LCA(x, y) 。

这样从 T(lx, ly) 转移到 T(x, y) 需要先转移到 T(x, ly)，再转移到 T(x, y) 。

从 T(lx, ly) 到 T(x, ly) : 我们用 xor 表示两个集合的对称差，就是出现两次的就会抵消。

那么 T(lx, ly) = S(lx, Root) xor S(ly, Root)

T(x, ly) = S(x, Root) xor S(ly, Root)

我们将上面两个式子的两边分别 xor 起来。

T(lx, ly) xor T(x, ly) = S(lx, Root) xor S(x, Root)

T(lx, ly) xor T(x, ly) = T(lx, x)

T(x, ly) = T(lx, ly) xor T(lx, x)

我们维护的是每个点是否在当前路径上，那么我们只需要将 T(lx, x) 上的点的状态改变，就实现了这个转移。

从 T(x, ly) 到 T(x, y) 同理。

实现了这个转移之后，我们就得到了 T(x, y) ，相比 S(x, y) 我们还需要将 LCA(x, y) 的状态改变，记录答案之后要再把 LCA 的状态改回去。因为我们需要维护的是 T(x, y)。

顺便说一下，使用的对树分块的方法，是王室联邦那道题的分块方法，维护一个栈。

目前在这道题的 Status 里的排名挨着 WJMZBMR 好开心~

46	930837	TomRiddle	23684 KB	80647 MS	C++	4776 B	2015-04-13 14:38:31
47	348468	WJMZBMR	12940 KB	80682 MS	C++	4383 B	2013-02-12 15:57:06

代码

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline void Read(int &Num)

{

	char c = getchar();

	bool Neg = false;

	while (c < '0' || c > '9')

	{

		if (c == '-') Neg = true;

		c = getchar();

	}

	Num = c - '0'; c = getchar();

	while (c >= '0' && c <= '9')

	{

		Num = Num * 10 + c - '0';

		c = getchar();

	}

	if (Neg) Num = -Num;

}

typedef long long LL;

const int MaxN = 100000 + 5, MaxQ = 100000 + 5;

int n, m, q, BlkSize, Top, Index, ID_Index, Chg_Index, Qt;

int V[MaxN], W[MaxN], Col[MaxN], Father[MaxN], ID[MaxN], Depth[MaxN], S[MaxN], Cnt[MaxN], Jump[MaxN][20], Ti[MaxN];

LL Ans;

LL AnsA[MaxQ];

bool InPath[MaxN];

struct Edge

{

	int v;

	Edge *Next;

} E[MaxN * 2], *P = E, *Point[MaxN];

inline void AddEdge(int x, int y)

{

	++P; P -> v = y;

	P -> Next = Point[x]; Point[x] = P;

}

void DFS(int x, int Fa, int Dep)

{

	Father[x] = Fa; Depth[x] = Dep;

	int Bottom = Top;

	for (Edge *j = Point[x]; j; j = j -> Next)

	{

		if (j -> v == Fa) continue;

		DFS(j -> v, x, Dep + 1);

		if (Top - Bottom >= BlkSize)

		{

			++ID_Index;

			while (Top > Bottom)

				ID[S[Top--]] = ID_Index;

		}

	}

	S[++Top] = x;

}

struct Query

{

	int x, y, vx, vy, tl, Idx;

} Q[MaxQ];

inline bool Cmp(Query q1, Query q2)

{

	if (q1.vx != q2.vx) return q1.vx < q2.vx;

	if (q1.vy != q2.vy) return q1.vy < q2.vy;

	return q1.tl < q2.tl;

}

struct Chg

{

	int Pos, Num, Prev;

} C[MaxQ];

inline void ChangeCol(int Num, int f)

{

	if (f == -1)

	{

		Ans -= (LL)V[Num] * (LL)W[Cnt[Num]];

		--Cnt[Num];

	}

	else

	{

		++Cnt[Num];

		Ans += (LL)V[Num] * (LL)W[Cnt[Num]];

	}

}

void ChangeTL(int x, int y)

{

	if (x == y) return;

	if (x < y)

	{

		for (int i = x + 1; i <= y; ++i)

		{

			if (InPath[C[i].Pos])

			{

				ChangeCol(Col[C[i].Pos], -1);

				ChangeCol(C[i].Num, 1);

			}

			Col[C[i].Pos] = C[i].Num;

		}

	}

	else

	{

		for (int i = x; i > y; --i)

		{

			if (InPath[C[i].Pos])

			{

				ChangeCol(Col[C[i].Pos], -1);

				ChangeCol(C[i].Prev, 1);

			}

			Col[C[i].Pos] = C[i].Prev;

		}

	}

}

inline void Reverse(int x)

{

	if (InPath[x])

	{

		InPath[x] = false;

		ChangeCol(Col[x], -1);

	}

	else

	{

		InPath[x] = true;

		ChangeCol(Col[x], 1);

	}

}

void Change(int x, int y)

{

	while (x != y)

	{

		if (Depth[x] < Depth[y]) swap(x, y);

		Reverse(x);

		x = Father[x];

	}

}

int LCA(int x, int y)

{

	if (Depth[x] < Depth[y]) swap(x, y);

	int Dif = Depth[x] - Depth[y];

	for (int i = 0; i <= 18; ++i)

		if (Dif & (1 << i)) x = Jump[x][i];

	if (x == y) return x;

	for (int i = 18; i >= 0; --i)

		if (Jump[x][i] != Jump[y][i])

		{

			x = Jump[x][i];

			y = Jump[y][i];

		}

	return Father[x];

}

void Prepare()

{

	for (int i = 1; i <= n; ++i) Jump[i][0] = Father[i];

	for (int j = 1; j <= 18; ++j)

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

			Jump[i][j] = Jump[Jump[i][j - 1]][j - 1];

}

int main()

{

	Read(n); Read(m); Read(q);

	for (int i = 1; i <= m; ++i) Read(V[i]);

	for (int i = 1; i <= n; ++i) Read(W[i]);

	int a, b;

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

	{

		Read(a); Read(b);

		AddEdge(a, b);

		AddEdge(b, a);

	}

	for (int i = 1; i <= n; ++i) Read(Col[i]);

	BlkSize = (int)pow(n, 0.667);

	DFS(1, 0, 0);

	while (Top > 0) ID[S[Top--]] = ID_Index;

	Prepare();

	for (int i = 1; i <= n; ++i) Ti[i] = Col[i];

	int f;

	for (int i = 1; i <= q; ++i)

	{

		Read(f); Read(a); Read(b);

		if (f == 0)

		{

			++Chg_Index;

			C[Chg_Index].Prev = Ti[a];

			Ti[a] = b;

			C[Chg_Index].Pos = a;

			C[Chg_Index].Num = b;

		}

		else

		{

			++Qt;

			Q[Qt].x = a; Q[Qt].y = b;

			Q[Qt].vx = ID[a]; Q[Qt].vy = ID[b];

			Q[Qt].tl = Chg_Index;

			Q[Qt].Idx = Qt;

		}

	}

	sort(Q + 1, Q + Qt + 1, Cmp);

	Ans = 0ll;

	ChangeTL(0, Q[1].tl);

	Change(Q[1].x, Q[1].y);

	int t = LCA(Q[1].x, Q[1].y);

	Reverse(t);

	AnsA[Q[1].Idx] = Ans;

	Reverse(t);

	for (int i = 2; i <= Qt; ++i)

	{

		ChangeTL(Q[i - 1].tl, Q[i].tl);

		Change(Q[i - 1].x, Q[i].x);

		Change(Q[i - 1].y, Q[i].y);

		t = LCA(Q[i].x, Q[i].y);

		Reverse(t);

		AnsA[Q[i].Idx] = Ans;

		Reverse(t);

	}

	for (int i = 1; i <= Qt; ++i) printf("%lld\n", AnsA[i]);

	return 0;

}

巴特西

[BZOJ 3052] [wc2013] 糖果公园【树上莫队】

题目分析

代码

最新文章

热门文章

巴特西

[BZOJ 3052] [wc2013] 糖果公园 【树上莫队】

题目分析

代码

最新文章

热门文章

[BZOJ 3052] [wc2013] 糖果公园【树上莫队】