【题解】LOJ 2130 「NOI2015」软件包管理器

Problem

给定一个树形依赖关系,求每次安装某个特定软件包或卸载软件需要改变多少个软件包的安装状态

Thought

如果要卸载一个软件包,需要将其子树中的软件包全部删除
如果要安装一个软件包,需要将其到根节点的软件包全部安装

可以发现这应该是一道数据结构题

删除子树中的软件包可以通过 $DFS$ 序,安装软件包可以直接处理到根节点的路径
那么很显然就是一道树链剖分裸题了

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

const int N = 100010;

struct edge {
    int t, n;
}e[N];
int head[N], tot;

int n, q;
int fa[N];
int dfn[N], low[N], DFN;
int siz[N], son[N], top[N];

char str[10];

#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
struct Tree {
    int num[N << 2], tag[N << 2];
    void pushdown(int x, int l, int r) {
        if(tag[x] == 1) {
            tag[L] = tag[R] = 1;
            num[L] = mid - l + 1;
            num[R] = r - mid;
        }
        else if(tag[x] == - 1) {
            tag[L] = tag[R] = - 1;
            num[L] = num[R] = 0;
        }
        tag[x] = 0;
    }
    void update(int x) {
        num[x] = num[L] + num[R];
    }
    int queryInstall(int x, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr)
            return num[x];
        if(tag[x]) pushdown(x, l, r);
        int ans = 0;
        if(mid >= ll)
            ans += queryInstall(L, l, mid, ll, rr);
        if(mid < rr)
            ans += queryInstall(R, mid + 1, r, ll, rr);
        return ans;
    }
    int queryUninstall(int x, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr)
            return r - l + 1 - num[x];
        if(tag[x]) pushdown(x, l, r);
        int ans = 0;
        if(mid >= ll)
            ans += queryUninstall(L, l, mid, ll, rr);
        if(mid < rr)
            ans += queryUninstall(R, mid + 1, r, ll, rr);
        return ans;
    }
    void add(int x, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr) {
            tag[x] = 1; num[x] = r - l + 1;
            return;
        }
        if(tag[x]) pushdown(x, l, r);
        if(mid >= ll)
            add(L, l, mid, ll, rr);
        if(mid < rr)
            add(R, mid + 1, r, ll, rr);
        update(x);
    }
    void del(int x, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr) {
            tag[x] = - 1; num[x] = 0;
            return;
        }
        if(tag[x]) pushdown(x, l, r);
        if(mid >= ll)
            del(L, l, mid, ll, rr);
        if(mid < rr)
            del(R, mid + 1, r, ll, rr);
        update(x);
    }
    void install(int x) {
        int ans = 0;
        while(1) {
            ans += queryUninstall(1, 1, n, dfn[top[x]], dfn[x]);
            add(1, 1, n, dfn[top[x]], dfn[x]);
            if(!top[x]) break;
            x = fa[top[x]];
        }
        printf("%d\n", ans);
    }
    void uninstall(int x) {
        printf("%d\n", queryInstall(1, 1, n, dfn[x], low[x]));
        del(1, 1, n, dfn[x], low[x]);
    }
}tr;

void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}

void dfs1(int x) {
    siz[x] = 1;
    for(int i = head[x]; i; i = e[i].n) {
        dfs1(e[i].t);
        siz[x] += siz[e[i].t];
        if(!son[x] || siz[son[x]] < siz[e[i].t])
            son[x] = e[i].t;
    }
}
void dfs2(int x, int T) {
    dfn[x] = ++ DFN; top[x] = T;
    if(son[x])
        dfs2(son[x], T);
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == son[x]) continue;
        dfs2(e[i].t, e[i].t);
    }
    low[x] = DFN;
}

int main() {
    n = read();
    for(int i = 1; i < n; ++ i)
        addedge(fa[i] = read(), i);
    dfs1(0); dfs2(0, 0);
    q = read();
    while(q --) {
        scanf("%s", str);
        if(str[0] == 'i')
            tr.install(read());
        else
            tr.uninstall(read());
    }
    return 0;
}
Comments

添加新评论