相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4196
解题报告
考虑树链剖分
线段树部分只需要支持区间赋值,查询区间中1的个数
总的时间复杂度:$O(n \log ^ 2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 200009; int n, m, head[N], nxt[N], to[N], beg[N], ot[N]; int fa[N], top[N], hvy[N], sz[N], dep[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } inline void DFS1(int w, int f) { fa[w] = f; dep[w] = dep[f] + 1; sz[w] = 1; for (int i = head[w]; i; i = nxt[i]) { DFS1(to[i], w); sz[w] += sz[to[i]]; if (sz[to[i]] > sz[hvy[w]]) { hvy[w] = to[i]; } } } inline void DFS2(int w, int t) { static int dfc = 0; beg[w] = ++dfc; top[w] = t; if (hvy[w]) { DFS2(hvy[w], t); for (int i = head[w]; i; i = nxt[i]) { if (to[i] != hvy[w]) { DFS2(to[i], to[i]); } } } ot[w] = dfc; } class Segment_Tree{ int cnt, root, ch[M][2], sum[M], tag[M]; public: inline void init() { init(root, 1, n); } inline int install(int w) { int ret = 0, tmp; while (true) { int l = beg[top[w]], r = beg[w], len = r - l + 1; tmp = len - modify(root, 1, n, beg[top[w]], beg[w], 1); ret += tmp; if (fa[top[w]] != w && tmp) { w = fa[top[w]]; } else { break; } } return ret; } inline int uninstall(int w) { return modify(root, 1, n, beg[w], ot[w], -1); } private: inline void init(int &w, int l, int r) { w = ++cnt; if (l < r) { int mid = l + r + 1 >> 1; init(ch[w][0], l, mid - 1); init(ch[w][1], mid, r); } } inline void PushDown(int w, int l, int mid, int r) { if (tag[w]) { int ls = ch[w][0], rs = ch[w][1]; if (tag[w] == 1) { sum[ls] = mid - l; sum[rs] = r - mid + 1; } else { sum[ls] = sum[rs] = 0; } tag[ls] = tag[rs] = tag[w]; tag[w] = 0; } } inline int modify(int w, int l, int r, int L, int R, int t) { if (L <= l && r <= R) { int ret = sum[w]; sum[w] = t == -1? 0: r - l + 1; tag[w] = t; return ret; } else { int mid = l + r + 1 >> 1, ret = 0; PushDown(w, l, mid, r); if (L < mid) { ret += modify(ch[w][0], l, mid - 1, L, R, t); } if (mid <= R) { ret += modify(ch[w][1], mid, r, L, R, t); } sum[w] = sum[ch[w][1]] + sum[ch[w][0]]; return ret; } } }SGT; int main() { freopen("manager.in", "r", stdin); freopen("manager.out", "w", stdout); n = read(); for (int i = 2; i <= n; i++) { AddEdge(read() + 1, i); } DFS1(1, 1); DFS2(1, 1); SGT.init(); m = read(); char cmd[20]; for (int i = 1; i <= m; i++) { scanf("%s", cmd + 1); if (cmd[1] == 'i') { printf("%d\n", SGT.install(read() + 1)); } else { printf("%d\n", SGT.uninstall(read() + 1)); } } return 0; }