软件包管理器

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3889 字
0..n-1号包构成依赖树。installx
一本通
练习
正文

/*
原题：T1562 「一本通 4.5 练习 2」软件包管理器（NOI2015）
题意：0..n-1 号包构成依赖树。install x 把 0→x 路径全置为已装(1)，输出本次改变数；
uninstall x 把 x 子树全置为未装(0)，输出改变数。
思路：HLD + 线段树区间覆盖(0/1)与区间求和。
install：改变数 = 路径长度 - 路径上已有的 1 的个数，再把路径整体置 1；
uninstall：改变数 = 子树中 1 的个数，再把子树整体置 0。
复杂度：时间 O((n+q)log^2 n)，空间 O(n)。
易错点：节点编号 0..n-1；install 是 0→x 路径，uninstall 是 x 的整棵子树；
统计改变数要分别用“已装数/0 的个数”，不能直接对整个区间赋值后读回。
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, q;
vector<int> g[MAXN];
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rk[MAXN], tim;
void dfs1(int u, int p){
    fa[u] = p;
    dep[u] = dep[p] + 1;
    sz[u] = 1;
    son[u] = 0;
    for(int v : g[u]){
        if(v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++tim;
    rk[tim] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int v : g[u]){
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
int sumv[4 * MAXN];
int setv[4 * MAXN];
void pushup(int o){
    sumv[o] = sumv[o * 2] + sumv[o * 2 + 1];
}
void pushdown(int o, int l, int r){
    if(setv[o] != -1){
        int mid = (l + r) / 2;
        setv[o * 2] = setv[o];
        sumv[o * 2] = setv[o] * (mid - l + 1);
        setv[o * 2 + 1] = setv[o];
        sumv[o * 2 + 1] = setv[o] * (r - mid);
        setv[o] = -1;
    }
}
void build(int o, int l, int r){
    setv[o] = -1;
    sumv[o] = 0;
    if(l == r) return;
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
}
void update(int o, int l, int r, int ql, int qr, int v){
    if(ql <= l && r <= qr){
        setv[o] = v;
        sumv[o] = v * (r - l + 1);
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    if(ql <= mid) update(o * 2, l, mid, ql, qr, v);
    if(qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, v);
    pushup(o);
}
int qres;
void query(int o, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr){
        qres += sumv[o];
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    if(ql <= mid) query(o * 2, l, mid, ql, qr);
    if(qr > mid) query(o * 2 + 1, mid + 1, r, ql, qr);
}
int path_sum(int u, int v){
    int res = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        qres = 0;
        query(1, 1, n, dfn[top[u]], dfn[u]);
        res += qres;
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    qres = 0;
    query(1, 1, n, dfn[u], dfn[v]);
    res += qres;
    return res;
}
int path_len(int u, int v){
    int res = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        res += dfn[u] - dfn[top[u]] + 1;
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    res += dfn[v] - dfn[u] + 1;
    return res;
}
void path_set(int u, int v, int val){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, 1, n, dfn[top[u]], dfn[u], val);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    update(1, 1, n, dfn[u], dfn[v], val);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n - 1; i++){
        int p;
        cin >> p;
        g[p].push_back(i);
        g[i].push_back(p);
    }
    dfs1(0, 0);
    dfs2(0, 0);
    build(1, 1, n);
    cin >> q;
    while(q--){
        string op;
        int x;
        cin >> op >> x;
        if(op == "install"){
            int len = path_len(0, x);
            int ones = path_sum(0, x);
            cout << len - ones << "\n";
            path_set(0, x, 1);
        }else{
            qres = 0;
            query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1);
            int sub = qres;
            cout << sub << "\n";
            update(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, 0);
        }
    }
    return 0;
}
软件包管理器

正文

一本通·提高篇的其它内容
