题目链接: https://www.luogu.org/problem/P2146
本题涉及算法:
树链剖分;
线段树 (区间更新及求和, 涉及懒惰标记)
然后对于每次 install x , 需要将 x 到 1 的路径上面的点全都置为 1.
那么在置为 1 之前统计一下节点数量 num1,
在置为 1 之后统计一下节点数量 num2,
答案就是 num2 - num1(当然, 也可以通过节点深度 dep[x] 来获得节点数量).
对于每次 unistall x, 需要将 x 为根的子树上面的点全都置为 0.
那么在置为 0 之前统计一下权值为 1 的节点数量 num1,
在置为 0 之后统计一下权值为 1 的节点数量 num2,
答案就是 num1-num2(当然, num2 其实就等于 0).
实现代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- #define INF (1<<29)
- const int maxn = 100010;
- int fa[maxn],
- dep[maxn],
- size[maxn],
- son[maxn],
- top[maxn],
- seg[maxn], seg_cnt,
- rev[maxn],
- n,
- sumv[maxn<<2], lazy[maxn<<2];
- vector<int> g[maxn];
- void dfs1(int u, int p) {
- size[u] = 1;
- for (vector<int>::iterator it = g[u].begin(); it != g[u].end(); it ++) {
- int v = (*it);
- if (v == p) continue;
- fa[v] = u;
- dep[v] = dep[u] + 1;
- dfs1(v, u);
- size[u] += size[v];
- if (size[v]>size[son[u]]) son[u] = v;
- }
- }
- void dfs2(int u, int tp) {
- seg[u] = ++seg_cnt;
- rev[seg_cnt] = u;
- top[u] = tp;
- if (son[u]) dfs2(son[u], tp);
- for (vector<int>::iterator it = g[u].begin(); it != g[u].end(); it ++) {
- int v = (*it);
- if (v == fa[u] || v == son[u]) continue;
- dfs2(v, v);
- }
- }
- #define lson l, mid, rt<<1
- #define rson mid+1, r, rt<<1|1
- void push_down(int rt, int len) {
- if (lazy[rt] != -1) {
- int l_len=len-len/2, r_len = len/2;
- lazy[rt<<1] = lazy[rt];
- lazy[rt<<1|1] = lazy[rt];
- sumv[rt<<1] = lazy[rt] * l_len;
- sumv[rt<<1|1] = lazy[rt] * r_len;
- lazy[rt] = -1;
- }
- }
- void push_up(int rt) {
- sumv[rt] = sumv[rt<<1] + sumv[rt<<1|1];
- }
- void build(int l, int r, int rt) {
- lazy[rt] = -1;
- int mid = (l + r) / 2;
- if (l == r) {
- sumv[rt] = 0;
- return;
- }
- build(lson); build(rson);
- push_up(rt);
- }
- void update(int L, int R, long long v, int l, int r, int rt) {
- if (L <= l && r <= R) {
- sumv[rt] = (r-l+1) * v;
- lazy[rt] = v;
- return;
- }
- push_down(rt, r-l+1);
- int mid = (l + r) / 2;
- if (L <= mid) update(L, R, v, lson);
- if (R> mid) update(L, R, v, rson);
- push_up(rt);
- }
- long long query_sum(int L, int R, int l, int r, int rt) {
- if (L <= l && r <= R) return sumv[rt];
- push_down(rt, r-l+1);
- int mid = (l + r) / 2;
- long long tmp = 0;
- if (L <= mid) tmp += query_sum(L, R, lson);
- if (R> mid) tmp += query_sum(L, R, rson);
- return tmp;
- }
- int t_ask(int u) {
- int res = 0;
- while (top[u] != 1) {
- res += query_sum(seg[top[u]], seg[u], 1, n, 1);
- u = fa[top[u]];
- }
- res += query_sum(seg[1], seg[u], 1, n, 1);
- return res;
- }
- void t_update(int u) {
- while (top[u] != 1) {
- update(seg[top[u]], seg[u], 1, 1, n, 1);
- u = fa[top[u]];
- }
- update(seg[1], seg[u], 1, 1, n, 1);
- }
- int m, x;
- string op;
- int main() {
- cin>> n;
- for (int i = 2; i <= n; i ++) {
- cin>> x;
- g[x+1].push_back(i);
- }
- dep[1] = fa[1] = 1;
- dfs1(1, -1);
- dfs2(1, 1);
- build(1, n, 1);
- cin>> m;
- while (m --) {
- cin>> op>> x;
- x ++;
- if (op == "install") {
- int num1 = t_ask(x);
- t_update(x);
- int num2 = t_ask(x);
- cout << num2 - num1 << endl;
- }
- else { // uninstall
- int num1 = query_sum(seg[x], seg[x]+size[x]-1, 1, n, 1);
- update(seg[x], seg[x]+size[x]-1, 0, 1, n, 1);
- int num2 = query_sum(seg[x], seg[x]+size[x]-1, 1, n, 1);
- cout << num1 - num2 << endl;
- }
- }
- return 0;
- }
作者: zifeiy
来源: http://www.bubuko.com/infodetail-3267242.html