「NOI 2015」软件包管理器 - 树链剖分

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

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

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

对于所有数据，\(n \leq 100000, \ q \leq 100000\)。

解题思路

本题是一个树上问题。由于是对路径上以及子树上的点操作，我们可以想到使用树链剖分解决。我们可以使用可以使用线段树维护每个点是否被安装，以及这条链或子树上安装的软件的数量。

接下来需要解决软件的安装卸载问题。对于安装软件 \(x\)，我们只需要将从根节点到 \(x\) 的这条路径上的所有软件安装即可；对于卸载软件 \(x\)，我们只需要将以 \(x\) 为根节点的子树中的所有软件删除即可。

维护时我们在线段树可处理懒标记 \(-1\)、\(0\)、\(1\) 三种值，分别表示无操作、将区间中所有数赋值为 \(0\)、将区间中所有数赋值为 \(1\)。序列中所有数只有 \(0\)、\(1\) 两种数，线段树维护区间和即可满足题目要求。

对于记录每次该边的状态，我们只需要在每次操作前先求出已安装的软件数量，然后和操作后的安装软件数量比较即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <cstdio>
#include <vector>

struct Node {
    std::vector<struct Edge> e;
    struct Chain *chain;
    int size, dfn, depth;
    Node *fa, *ch;
};

struct Edge {
    Node *s, *t;

    Edge(Node *s, Node *t) : s(s), t(t) {}
};

struct Chain {
    Node *top;

    Chain(Node *top) : top(top) {}
};

inline void addEdge(Node *u, Node *v) {
    u->e.push_back(Edge(u, v));
    v->e.push_back(Edge(v, u));
}

void dfs1(Node *v, Node *fa = nullptr) {
    v->size = 1;

    for (Edge &e : v->e) {
        if (e.t == fa) continue;
        e.t->fa = v;
        e.t->depth = v->depth + 1;
        dfs1(e.t, v);
        v->size += e.t->size;
        if (!v->ch || v->ch->size < e.t->size) v->ch = e.t;
    }
}

void dfs2(Node *v) {
    static int ts = 0;
    v->dfn = ++ts;

    if (!v->fa || v != v->fa->ch) v->chain = new Chain(v);
    else v->chain = v->fa->chain;

    if (v->ch) dfs2(v->ch);
    for (Edge &e : v->e) {
        if (e.t->fa == v && e.t != v->ch) {
            dfs2(e.t);
        }
    }
}

inline void split(Node *v) {
    v->depth = 1;
    dfs1(v);
    dfs2(v);
}

struct SegT {
    int l, r;
    SegT *lc, *rc;
    int val, tag;

    SegT(int l, int r, SegT *lc, SegT *rc) : l(l), r(r), lc(lc), rc(rc), val(0), tag(-1) {}

    void cover(const int delta) {
        if (delta == -1) return;
        val = delta == 1 ? r - l + 1 : 0;
        tag = delta == 1 ? 1 : 0;
    }

    void pushDown() {
        if (tag != -1) {
            lc->cover(tag);
            rc->cover(tag);
            tag = -1;
        }
    }

    void update(const int l, const int r, const int delta) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) cover(delta);
        else {
            pushDown();
            lc->update(l, r, delta);
            rc->update(l, r, delta);
            val = lc->val + rc->val;
        }
    }

    static SegT *build(const int l, const int r) {
        if (l > r) return nullptr;
        else if (l == r) return new SegT(l, r, nullptr, nullptr);
        else {
            const int mid = l + (r - l) / 2;
            return new SegT(l, r, build(l, mid), build(mid + 1, r));
        }
    }
} *segment;

inline void update(Node *u, Node *v, int w) {
    while (u->chain != v->chain) {
        if (u->chain->top->depth < v->chain->top->depth) std::swap(u, v);
        segment->update(u->chain->top->dfn, u->dfn, w);
        u = u->chain->top->fa;
    }

    if (u->depth > v->depth) std::swap(u, v);
    segment->update(u->dfn, v->dfn, w);
}

int main() {
    int n;
    scanf("%d", &n);

    std::vector<Node> nodes(n);
    for (int i = 1; i < n; i++) {
        int p;
        scanf("%d", &p);
        addEdge(&nodes[p], &nodes[i]);
    }

    split(&nodes[0]);
    segment = SegT::build(1, n);

    int q;
    scanf("%d", &q);
    while (q--) {
        char op[sizeof("uninstall")];
        int x;
        scanf("%s %d", op, &x);

        int bef = segment->val;

        if (op[0] == 'i') {
            update(&nodes[0], &nodes[x], 1);
            printf("%d\n", segment->val - bef);
        } else if (op[0] == 'u') {
            segment->update(nodes[x].dfn, nodes[x].dfn + nodes[x].size - 1, 0);
            printf("%d\n", bef - segment->val);
        }
    }

    return 0;
}