BZOJ4196——noi2015软件包管理器

1、题目大意：讲道理，就是让你有两个修改一个是把一个点到根的路径上的点权值全部变成1，另一个是把一个子树全部变成0

然后让你输出每次修改，改变的哪些节点的值

2、分析：就是一个树剖，树剖是满足dfs序的，然后我们就相当于建了一个既符合树剖，又满足dfs序的线段树，然后就在线段树上询
问就可以了

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1000000
struct tree_chain_parition{
    int Size[M], Top[M], Fa[M], Height[M], num[M];
    int tot, ST_tot;
    int left[M], right[M];
    int son[M], head[M], Next[M];
    int n;
    int q[M], lazy[M];
    inline void init(){
        memset(head, -1, sizeof(head));
        memset(lazy, -1, sizeof(lazy));
        tot = ST_tot = 0;
        Top[1] = 1;
    }
    inline void pushdown(int l, int r, int o){
        int mid = (l + r) / 2;
        if(lazy[o] != -1){
            q[2 * o] = (mid - l + 1) * lazy[o];
            q[2 * o + 1] = (r - mid) * lazy[o];
            lazy[2 * o] = lazy[2 * o + 1] = lazy[o];
            lazy[o] = -1;
        }
    }
    inline void add(int l, int r, int o, int x, int y, int k){
        if(x <= l && r <= y){
            q[o] = (r - l + 1) * k;
            lazy[o] = k;
            return;
        }
        pushdown(l, r, o);
        int mid = (l + r) / 2;
        if(x <= mid) add(l, mid, 2 * o, x, y, k);
        if(y > mid) add(mid + 1, r, 2 * o + 1, x, y, k);
        q[o] = q[2 * o] + q[2 * o + 1];
    }
    inline int query(int l, int r, int o, int x, int y){
        if(x <= l && r <= y){
            return q[o];
        }
        pushdown(l, r, o);
        int mid = (l + r) / 2;
        int ret = 0;
        if(x <= mid) ret += query(l, mid, 2 * o, x, y);
        if(y > mid) ret += query(mid + 1, r, 2 * o + 1, x, y);
        return ret;
    }
    inline int insert(int x, int y){
        tot ++;
        son[tot] = y;
        Next[tot] = head[x];
        head[x] = tot;
    }
    inline void dfs1(int x, int fa, int height){
        Height[x] = height;
        Fa[x] = fa;
        for(int i = head[x]; i != -1; i = Next[i]){
            dfs1(son[i], x, height + 1);
            Size[x] += Size[son[i]];
        }
        Size[x] ++;
    }
    inline void dfs2(int x, int fa){
        ST_tot ++;
        num[x] = ST_tot;
        left[x] = ST_tot;
        int o = 0, ss = 0;
        for(int i = head[x]; i != -1; i = Next[i]){
            if(Size[son[i]] > ss){
                o = i;
                ss = Size[son[i]];
            }
        }
        if(o != 0){
            Top[son[o]] = Top[x];
            dfs2(son[o], x);
        }
        for(int i = head[x]; i != -1; i = Next[i]) if(o != i){
            Top[son[i]] = son[i];
            dfs2(son[i], x);
        }
        right[x] = ST_tot;
    }
    inline int Install(int x){
        int y = 1;
        int ret = 0;
        while(Top[x] != Top[y]){
            if(Height[Top[x]] < Height[Top[y]]) swap(x, y);
            ret += (num[x] - num[Top[x]] + 1) - query(1, n, 1, num[Top[x]], num[x]);
            add(1, n, 1, num[Top[x]], num[x], 1);
            x = Fa[Top[x]];
        }
        if(Height[x] < Height[y]) swap(x, y);
        ret += (num[x] - num[y] + 1) - query(1, n, 1, num[y], num[x]);
        add(1, n, 1, num[y], num[x], 1);
        return ret;
    }
    inline int Unstall(int x){
        int ret = query(1, n, 1, left[x], right[x]);
        add(1, n, 1, left[x], right[x], 0);
        return ret;
    }
} wt;
int main(){
    int n;
    scanf("%d", &n);
    wt.n = n;
    wt.init();
    for(int i = 2; i <= n; i ++){
        scanf("%d", &wt.Fa[i]);
        wt.Fa[i] ++;
        wt.insert(wt.Fa[i], i);
    }
    wt.dfs1(1, -1, 1);
    wt.dfs2(1, -1);
    int m;
    scanf("%d", &m);
    char str[20];
    int x;
    for(int i = 1; i <= m; i ++){
        scanf("%s%d", str, &x);
        x ++;
        if(str[0] == 'i'){
            printf("%d\n", wt.Install(x));
        }
        else printf("%d\n", wt.Unstall(x));
    }
    return 0;
}

巴特西

BZOJ4196——noi2015软件包管理器

最新文章

热门文章