自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 21:53:14，当前版本为作者最后更新于2018-11-27 16:02:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述：

题面说的很清楚了。

题解：

考虑建立一棵每个节点都表示一个版本的树。

以初始版本 $0$ 为根。对于第 $i$ 个操作，从 $v_i$ 向 $i$ 连一条边，而边权则是 $opt_i$ 和 $x_i$ 的二元组，表示经过这条边上操作，可以达到下一个状态。

考虑使用权值树状数组维护操作。只需要实现单点加，查询前缀和以及树状数组上二分的操作即可。

树状数组提前插入 $-2147483647$ 和 $2147483647$ 两个数，方便统计。

因为权值范围太大，所以先离散化权值，再插入树状数组。

只需要从结点 $0$ 开始 DFS ，进入子树时执行操作，退出子树时撤销操作即可。

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 0x7fffffff;
const int MQ = 500010;

int N, Q;
int faz[MQ], opt[MQ], a[MQ], b[MQ];
int Ans[MQ];

int eh[MQ], nxt[MQ], to[MQ], tot;
inline void ins(int x, int y) {
	nxt[++tot] = eh[x]; to[tot] = y; eh[x] = tot;
}

int B[MQ];
inline void Add(int i, int x) { for (; i <= N; i += i & -i) B[i] += x; }
inline int Qur(int i) { int A = 0; for (; i; i -= i & -i) A += B[i]; return A; }
inline int BS(int x) { int p = 0; for (int j = 1 << 18; j; j >>= 1) if ((p | j) <= N && B[p | j] <= x) x -= B[p |= j]; return p;}

void DFS(int u, int o, int x) {
	int ok = 1;
	if (o == 1) Add(x, 1);
	if (o == 2) {
		if (Qur(x) == Qur(x - 1)) ok = 0;
		else Add(x, -1);
	}
	if (o == 3) Ans[u] = Qur(x - 1);
	if (o == 4) Ans[u] = b[BS(x) + 1];
	if (o == 5) Ans[u] = b[BS(Qur(x - 1) - 1) + 1];
	if (o == 6) Ans[u] = b[BS(Qur(x)) + 1];
	
	for (int i = eh[u]; i; i = nxt[i])
		DFS(to[i], opt[to[i]], a[to[i]]);
	
	if (o == 1) Add(x, -1);
	if (o == 2 && ok) Add(x, 1);
}

int main() {
	scanf("%d", &Q);
	for (int i = 1; i <= Q; ++i) {
		scanf("%d%d%d", &faz[i], &opt[i], &a[i]);
		if (opt[i] != 4)
			b[++N] = a[i];
	} b[++N] = -INF, b[++N] = INF;
	sort(b + 1, b + N + 1);
	N = unique(b + 1, b + N + 1) - b - 1;
	for (int i = 1; i <= Q; ++i) {
		ins(faz[i], i);
		if (opt[i] != 4)
			a[i] = lower_bound(b + 1, b + N + 1, a[i]) - b;
	}
	Add(1, 1), Add(N, 1);
	DFS(0, 0, 0);
	for (int i = 1; i <= Q; ++i) {
		if(opt[i] > 2)
			printf("%d\n", Ans[i]);
	}
	return 0;
}