-树链剖分-线段树- [洛谷 P2146][NOI2015]软件包管理器

题目描述

Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,⋯,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，A[m-1]依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

输入格式

从文件manager.in中读入数据。

输入文件的第1行包含1个整数n，表示软件包的总数。软件包从0开始编号。

随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。

接下来一行包含1个整数q，表示询问的总数。之后q行，每行1个询问。询问分为两种：

install x：表示安装软件包x

uninstall x：表示卸载软件包x

你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出格式

输出到文件manager.out中。

输出文件包括q行。

输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。

输入样例

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

输出样例

3
1
3
2
3

Solution

如果用1表示已安装，0表示未安装，那么先将这道题转换成人话：

操作install：统计x到根节点路径上为0的节点个数并输出，并把这一路径上的节点都赋值为1

操作uninstall：统计以x为根的子树的节点为1的个数，并把这个子树上的节点都赋值为0

然后这道题就很好理解了。

如何解决第一个操作呢，很简单，先统计出节点为1的个数，再用x的深度-节点为1的个数，然后再用线段树的区间覆盖就可以了

那么第二个操作呢，也很简单，直接统计子树上1的个数，然后再覆盖。

下面是~~愉快的~~代码时间：

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
#define INF 0x7fffffff
#define MAXN 5000000
#define abs(x) ((x) < 0 ? (-x) : (x))
int max(int a, int b) {
    if (a > b) return a;
    else return b;
}
void swap(int &x, int &y) {
    int t = x;
    x = y;
    y = t;
}
struct Edge {
    int v, nx;
}e[MAXN];
int head[MAXN], ecnt, n, m, x, y, dep[MAXN], si[MAXN], wt[MAXN], w[MAXN], fat[MAXN];
int fa[MAXN], top[MAXN], son[MAXN], cnt, r = 1, id[MAXN], f[MAXN];
void add(int f, int t) {
    e[++ecnt] = (Edge) {t, head[f]};
    head[f] = ecnt;
}
struct Segtree {
    int a[MAXN], b[MAXN << 2], lazy[MAXN << 2];
    void pd(int p) {
        b[p] = b[ls(p)] + b[rs(p)];
    }
    void build(int l, int r, int p) {
        lazy[p] = -1;
        if (l == r) {
            b[p] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(l, m, ls(p));
        build(m + 1, r, rs(p));
        pd(p);
    }
    void f(int p, int l, int r, int k) {
        lazy[p] = k;
        b[p] = k * (r - l + 1);
        return;
    }
    void pushd(int p, int l, int r) {
        if (lazy[p] != -1) {
            int m = (l + r) >> 1;
            f(ls(p), l, m, lazy[p]);
            f(rs(p), m + 1, r, lazy[p]);
            lazy[p] = -1;
        }
    }
    void updater(int x, int y, int l, int r, int p, int k) {
        if (x <= l && y >= r) {
            lazy[p] = k;
            b[p] = k * (r - l + 1);
            return;
        }
        pushd(p, l, r);
        int m = (l + r) >> 1;
        if (x <= m) updater(x, y, l, m, ls(p), k);
        if (y > m) updater(x, y, m + 1, r, rs(p), k);
        pd(p);
    }
    int qsum(int x, int y, int l, int r, int p) {
        int s = 0;
        if (x <= l && y >= r) {
            return b[p];
        }
        int m = (l + r) >> 1;
        pushd(p, l, r);
        if (x <= m) s += qsum(x, y, l, m, ls(p));
        if (y > m) s += qsum(x, y, m + 1, r, rs(p));
        return s;
    }
}tree;
void dfs1(int u, int f, int deep) {
    dep[u] = deep;
    fa[u] = f;
    si[u] = 1;
    for (int i = head[u]; i; i = e[i].nx) {
        int to = e[i].v;
        if (to == f) continue;
        dfs1(to, u, deep + 1);
        si[u] += si[to];
        if (si[to] > si[son[u]]) son[u] = to;
    }
}
void dfs2(int u, int topf) {
    id[u] = ++cnt;
    wt[cnt] = w[u];
    top[u] = topf;
    if (!son[u]) return;
    dfs2(son[u], topf);
    for (int i = head[u]; i; i = e[i].nx) {
        int to = e[i].v;
        if (fa[u] == to || to == son[u]) continue;
        dfs2(to, to);
    }
}
inline void upr(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        tree.updater(id[top[x]], id[x], 1, n, 1, k);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    tree.updater(id[x], id[y], 1, n, 1, k);
}
inline int tq(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += tree.qsum(id[top[x]], id[x], 1, n, 1);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans += tree.qsum(id[x], id[y], 1, n, 1);
    return ans;
}
inline void ups(int x, int k) {
    tree.updater(id[x], id[x] + si[x] - 1, 1, n, 1, k);
}
inline int qs(int x) {
    return tree.qsum(id[x], id[x] + si[x] - 1, 1, n, 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &x);
        x++;
        fat[i]++;
        add(i, x);
        add(x, i);
    }
    dfs1(r, -1, 1);
    dfs2(r, r);
    tree.build(1, n, 1);
    scanf("%d", &m);
    while (m--) {
        char op[20];
        scanf("%s", op);
        if (op[0] == 'i') {
            scanf("%d", &x);
            x++;
            printf("%d\n", dep[x] - tq(x, r));
            upr(x, r, 1);
        }
        if (op[0] == 'u') {
            scanf("%d", &x);
            x++;
            printf("%d\n", qs(x));
            ups(x, 0);
        }
    }
}