【数据结构树树链剖分】luogu_2146 [NOI2015]软件包管理器

本文主要是介绍【数据结构树树链剖分】luogu_2146 [NOI2015]软件包管理器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个以树表达的关系，每次选择一个点安装或卸载。

如果卸载，那么它儿子们都要卸载。
如果安装，那么它父亲们都要安装。

求每次操作改变了多少点的状态。

思路

剖成链然后就是傻逼题。

代码

#include <cctype>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>struct segmentTree {int ls, rs, l, r, sum, lazy;
}t[400001];
int father[100001], dep[100001], size[100001], son[100001], rev[100001], top[100001], seg[100001];
int head[100001], ver[200001], next[200001];
int n, m, tot, cnt;inline void add(int u, int v) {ver[++tot] = v;next[tot] = head[u];head[u] = tot;
}void dfs1(int u, int fa) {father[u] = fa;size[u] = 1;dep[u] = dep[fa] + 1;for (int i = head[u]; i; i = next[i]) {if (ver[i] == fa) continue;dfs1(ver[i], u);size[u] += size[ver[i]];if (size[ver[i]] > size[son[u]] || !son[u]) son[u] = ver[i];}
}void dfs2(int u, int t) {top[u] = t;seg[u] = ++cnt;rev[cnt] = u;if (!son[u]) return;dfs2(son[u], t);for (int i = head[u]; i; i = next[i]) {if (ver[i] == father[u] || son[u] == ver[i]) continue;dfs2(ver[i], ver[i]);}
}void build(int p, int l, int r) {t[p].l = l, t[p].r = r, t[p].lazy = -1;if (l == r) return;int mid = l + r >> 1;build(t[p].ls = ++cnt, l, mid);build(t[p].rs = ++cnt, mid + 1, r);
}inline void spread(int p) {t[t[p].ls].lazy = t[t[p].rs].lazy = t[p].lazy;t[t[p].ls].sum = (t[t[p].ls].r - t[t[p].ls].l + 1) * t[p].lazy;t[t[p].rs].sum = (t[t[p].rs].r - t[t[p].rs].l + 1) * t[p].lazy;t[p].lazy = -1;
}int query(int p, int l, int r) {if (l <= t[p].l && t[p].r <= r)return t[p].sum;if (t[p].lazy != -1) spread(p);int mid = t[p].l + t[p].r >> 1, res = 0;if (l <= mid) res += query(t[p].ls, l, r);if (r > mid) res += query(t[p].rs, l, r);return res;
}void update(int p, int l, int r, int val) {if (l <= t[p].l && t[p].r <= r) {t[p].sum = (t[p].r - t[p].l + 1) * val;t[p].lazy = val;return;}if (t[p].lazy != -1) spread(p);int mid = t[p].l + t[p].r >> 1;if (l <= mid) update(t[p].ls, l, r, val);if (r > mid) update(t[p].rs, l, r, val);t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum;
}inline int ask(int x) {int fx = top[x], res = 0;while (fx) {res += seg[x] - seg[fx] + 1 - query(1, seg[fx], seg[x]);update(1, seg[fx], seg[x], 1);x = father[fx];fx = top[x];}res += seg[x] - seg[fx] + 1 - query(1, seg[fx], seg[x]);update(1, seg[fx], seg[x], 1);return res;
}signed main() {scanf("%d", &n);for (register int i = 1; i < n; i++) {int x;scanf("%d", &x);add(x, i), add(i, x);}dfs1(0, -1);dfs2(0, 0);build(cnt = 1, 1, n);scanf("%d", &m);std::string op;for (int x; m; m--) {std::cin >> op;if (op == "install") {scanf("%d", &x);printf("%d\n", ask(x));} else {scanf("%d", &x);printf("%d\n", query(1, seg[x], seg[x] + size[x] - 1));update(1, seg[x], seg[x] + size[x] - 1, 0);}}
}