题目传送门：洛谷P3835。
题意简述：
题面说的很清楚了。
题解：
考虑建立一棵每个节点都表示一个版本的树。
以初始版本 \(0\) 为根。对于第 \(i\) 个操作，从 \(v_i\) 向 \(i\) 连一条边，而边权则是 \(opt_i\) 和 \(x_i\) 的二元组，表示经过这条边上操作，可以达到下一个状态。
考虑使用权值树状数组维护操作。只需要实现单点加，查询前缀和以及树状数组上二分的操作即可。
树状数组提前插入 \(-2147483647\) 和 \(2147483647\) 两个数，方便统计。
因为权值范围太大，所以先离散化权值，再插入树状数组。
只需要从结点 \(0\) 开始 DFS ，进入子树时执行操作，退出子树时撤销操作即可。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int INF = 0x7fffffff; 6 const int MQ = 500010; 7 8 int N, Q; 9 int faz[MQ], opt[MQ], a[MQ], b[MQ]; 10 int Ans[MQ]; 11 12 int eh[MQ], nxt[MQ], to[MQ], tot; 13 inline void ins(int x, int y) { 14 nxt[++tot] = eh[x]; to[tot] = y; eh[x] = tot; 15 } 16 17 int B[MQ]; 18 inline void Add(int i, int x) { for (; i <= N; i += i & -i) B[i] += x; } 19 inline int Qur(int i) { int A = 0; for (; i; i -= i & -i) A += B[i]; return A; } 20 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;} 21 22 void DFS(int u, int o, int x) { 23 int ok = 1; 24 if (o == 1) Add(x, 1); 25 if (o == 2) { 26 if (Qur(x) == Qur(x - 1)) ok = 0; 27 else Add(x, -1); 28 } 29 if (o == 3) Ans[u] = Qur(x - 1); 30 if (o == 4) Ans[u] = b[BS(x) + 1]; 31 if (o == 5) Ans[u] = b[BS(Qur(x - 1) - 1) + 1]; 32 if (o == 6) Ans[u] = b[BS(Qur(x)) + 1]; 33 34 for (int i = eh[u]; i; i = nxt[i]) 35 DFS(to[i], opt[to[i]], a[to[i]]); 36 37 if (o == 1) Add(x, -1); 38 if (o == 2 && ok) Add(x, 1); 39 } 40 41 int main() { 42 scanf("%d", &Q); 43 for (int i = 1; i <= Q; ++i) { 44 scanf("%d%d%d", &faz[i], &opt[i], &a[i]); 45 if (opt[i] != 4) 46 b[++N] = a[i]; 47 } b[++N] = -INF, b[++N] = INF; 48 sort(b + 1, b + N + 1); 49 N = unique(b + 1, b + N + 1) - b - 1; 50 for (int i = 1; i <= Q; ++i) { 51 ins(faz[i], i); 52 if (opt[i] != 4) 53 a[i] = lower_bound(b + 1, b + N + 1, a[i]) - b; 54 } 55 Add(1, 1), Add(N, 1); 56 DFS(0, 0, 0); 57 for (int i = 1; i <= Q; ++i) { 58 if(opt[i] > 2) 59 printf("%d\n", Ans[i]); 60 } 61 return 0; 62 }