【BZOJ 3735】苹果树 树上莫队(树分块+离线莫队+鬼畜的压行)

时间：2022-05-26 21:27:14

2016-05-09 UPD：学习了新的DFS序列分块，然后发现这个东西是战术核导弹？反正比下面的树分块不知道要快到哪里去了

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 50003;

const int M = 100003;

void read(int &k) {

	k = 0; int fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 1) + (k << 3) + c - '0';

	k = k * fh;

}

struct node {int nxt, to;} E[N << 1];

struct quest {int l, r, id, a, b, lca;} Q[M];

int f[N][17], pos[N << 1], L[N], R[N], color[N], cal[N];

int point[N], bel[N << 1], ans = 0, cnt = 0, n, m, A[M], deep[N];

bool vis[N];

void ins(int x, int y) {E[++cnt].nxt = point[x]; E[cnt].to = y; point[x] = cnt;}

void _(int x, int fa) {

	pos[L[x] = ++cnt] = x;

	for(int i = 1; i <= 16; ++i) {f[x][i] = f[f[x][i - 1]][i - 1]; if (f[x][i] == 0) break;}

	for(int tmp = point[x]; tmp; tmp = E[tmp].nxt)

		if (E[tmp].to != fa)

			{deep[E[tmp].to] = deep[x] + 1; f[E[tmp].to][0] = x; _(E[tmp].to, x);}

	pos[R[x] = ++cnt] = x;

}

int LCA(int x, int y) {

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

	int d = deep[x] - deep[y];

	for(int i = 0; i <= 16; ++i) if (d & (1 << i)) x = f[x][i];

	if (x == y) return x;

	for(int i = 16; i >= 0; --i) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];

	return f[x][0];

}

bool cmp(quest A, quest B) {return bel[A.l] == bel[B.l] ? A.r < B.r : A.l < B.l;}

int check(int a, int b) {return cal[a] && cal[b] && a != b;}

void update(int x) {

	if (vis[x]) {if (!(--cal[color[x]])) --ans;}

	else {if (!(cal[color[x]]++)) ++ans;}

	vis[x] = !vis[x];

}

int main() {

	read(n); read(m);

	for(int i = 1; i <= n; ++i) read(color[i]);

	int lca, u, v, a, b;

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

		read(u); read(v);

		ins(u, v); ins(v, u);

	}

	cnt = 0;

	_(1, 0);

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

		read(u); read(v); read(Q[i].a); read(Q[i].b); Q[i].id = i;

		lca = LCA(u, v);

		if (L[u] > L[v]) swap(u, v);

		if (u != lca) {Q[i].l = R[u]; Q[i].r = L[v]; Q[i].lca = lca;}

		else {Q[i].l = L[u]; Q[i].r = L[v]; Q[i].lca = 0;}

	}

	int nn = n << 1, sq = sqrt(nn + 0.5), tmp = 0; cnt = 1;

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

		bel[i] = tmp;

		++cnt; if (cnt > sq) cnt = 1, ++tmp;

	}

	sort(Q + 1, Q + m + 1, cmp);

	int l = 1, r = 0, tol, tor;

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

		tol = Q[i].l; tor = Q[i].r;

		while (l < tol) update(pos[l++]);

		while (l > tol) update(pos[--l]);

		while (r < tor) update(pos[++r]);

		while (r > tor) update(pos[r--]);

		if (Q[i].lca) update(Q[i].lca);

		A[Q[i].id] = ans - check(Q[i].a, Q[i].b);

		if (Q[i].lca) update(Q[i].lca);

	}

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

		printf("%d\n", A[i]);

	return 0;

}

学习了树上莫队，树分块后对讯问的$dfs序$排序，然后就可以滑动树链处理答案了。

关于树链的滑动，只需要特殊处理一下$LCA$就行了。

在这里一条树链保留下来给后面的链来转移的$now$的为这条树链上所有点除去$LCA$的颜色种数。因为如果要考虑$LCA$情况就太多了，不如单独考虑$LCA$。

转移后加上当前链的$LCA$进行统计，然后再去掉这个$LCA$更新一下$now$值给后面的链转移。

这都是我的理解，说的有点不清楚，具体请看vfk的题解 OTZ 虽然不是这道题，但是通过这篇博客学习树上莫队也是很好的。

PS：压行大法使代码看起来像一堵墙

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 50003

#define M 100003

#define read(x) x=getint()

using namespace std;

inline int getint() {int k = 0, fh = 1; char c = getchar();	for(; c < '0' || c > '9'; c = getchar()) if (c == '-') fh = -1; for(; c >= '0' && c <= '9'; c = getchar()) k = k * 10 + c - '0'; return k * fh;}

int n, m, color[N], cnt = 0, fa[N][16], deep[N], dfn[N << 1], now = 0;

int belong[N], cntblo = 0, sqrblo, top = 0, sta[N], ans[M], colsum[N], point[N];

short v[N];

struct Enode {int nxt, to;} E[N << 1];

struct node {int x, y, a, b, id;} q[M];

inline bool cmp(node A, node B) {return belong[A.x] == belong[B.x] ? dfn[A.y] < dfn[B.y] : dfn[A.x] < dfn[B.x];}

inline void ins(int x, int y) {E[++cnt].nxt = point[x]; E[cnt].to = y; point[x] = cnt;}

inline void dfs(int x) {

	dfn[x] = ++cnt;

	int mark = top;

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

		fa[x][i] = fa[fa[x][i - 1]][i - 1];

	for(int tmp = point[x]; tmp; tmp = E[tmp].nxt) {

		int v = E[tmp].to;

		if (v == fa[x][0]) continue;

		deep[v] =deep[x] + 1;

		fa[v][0] = x;

		dfs(v);

		if (top - mark >= sqrblo) {

			++cntblo;

			while (top != mark)

				belong[sta[top--]] = cntblo;

		}

	}

	sta[++top] = x;

}

inline int LCA(int x, int y) {

	if (deep[x] < deep[y])

		swap(x, y);

	int k = deep[x] - deep[y];

	for(int j = 15; j >= 0; --j)

		if (k & (1 << j))

			x = fa[x][j];

	if (x == y) return x;

	for(int j = 15; j >= 0; --j)

		if (fa[x][j] != fa[y][j])

			x = fa[x][j], y = fa[y][j];

	return fa[x][0];

}

inline void pushup(int x) {

	if (v[x]) {

		--colsum[color[x]];

		if (!colsum[color[x]])

			--now;

	} else {

		if (!colsum[color[x]])

			++now;

		++colsum[color[x]];

	}

	v[x] ^= 1;

}

inline void change(int x, int y) {

	while (x != y) {

		if (deep[x] < deep[y])

			pushup(y), y = fa[y][0];

		else

			pushup(x), x = fa[x][0];

	} //O)Z这个方法好神啊！！！我为什么想不到一个一个往上跳呢QAQ

}

int main() {

	read(n); read(m);

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

		read(color[i]);

	int u, v;

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

		read(u); read(v);

		if (u == 0 || v == 0) continue;

		ins(u, v);

		ins(v, u);

	}

	sqrblo = ceil(sqrt(n));

	cnt = 0;

	dfs(1);

	while (top)

		belong[sta[top--]] = cntblo;

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

		read(q[i].x); read(q[i].y); read(q[i].a); read(q[i].b); q[i].id = i;

		if (dfn[q[i].x] > dfn[q[i].y])

			swap(q[i].x, q[i].y);

	}

	sort(q + 1, q + m + 1, cmp);

	q[0].x = q[0].y = 1;

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

		change(q[i - 1].x, q[i].x);

		change(q[i - 1].y, q[i].y);

		int lca = LCA(q[i].x, q[i].y);

		pushup(lca);

		ans[q[i].id] = now;

		if (colsum[q[i].a] && colsum[q[i].b] && q[i].a != q[i].b)

			--ans[q[i].id];

		pushup(lca);

	}

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

		printf("%d\n", ans[i]);

	return 0;

}

$SDOI2016 Round1$之前做的最后一道题了，希望省选不要爆零啊$QAQ$

相关文章