P2146 [NOI2015]软件包管理器

淩亂°似流年 2023-06-04 08:00 71阅读 0赞

[题目链接][Link 1]

**虽然是NOI的题，其实自己想想也就可以做出来。先按题目中的依赖关系建造一颗树，初始的时候所有点权设为0，然后就是快乐的树剖。安装的话就是从节点到根节点的路径的点权值全部赋为1，删除则是把该节点及其子树的权值全部赋为0。统计操作前后两次的区间和，两次差值的绝对值即为答案。这样的好处就是之前已经安装或者删除的点的状态不会有影响，便于维护。其实就是区间覆盖板子。**

**代码如下，好像BZOJ老年机还要TLE**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    int a[maxn];
    int n,m,x; 
    struct node{
        int nxt,to;
    }edge[maxn*2];
    int head[maxn],cnt;
    struct node2{
        int l,r,lazy,sum;
    }tree[maxn*4];
    char opt[666];
    void add(int x,int y){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;
        head[x]=cnt;
    }
    int fa[maxn],son[maxn],size[maxn],top[maxn],dep[maxn],id[maxn],w[maxn],Time;
    void dfs1(int x,int f){
        size[x]=1;
        fa[x]=f;
        dep[x]=dep[f]+1;
        int maxson=-1;
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[x]) continue;
            dfs1(v,x);
            size[x]+=size[v];
            if(size[v]>maxson){
                maxson=size[v];
                son[x]=v;
            }
        }
    }
    void dfs2(int x,int topf){
        top[x]=topf;
        id[x]=++Time;
        if(!son[x]) return;
        dfs2(son[x],topf);
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==son[x]||v==fa[x]) continue;
            dfs2(v,v);
        }
    }
    void build(int now,int l,int r){
        tree[now].l=l,tree[now].r=r,tree[now].lazy=-1;
        if(l==r) return;
        int mid=(tree[now].l+tree[now].r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    }
    void pushdown(int now){
        if(tree[now].lazy!=-1){
            tree[now<<1].sum=(tree[now<<1].r-tree[now<<1].l+1)*tree[now].lazy;
            tree[now<<1|1].sum=(tree[now<<1|1].r-tree[now<<1|1].l+1)*tree[now].lazy;
            tree[now<<1].lazy=tree[now].lazy;
            tree[now<<1|1].lazy=tree[now].lazy;
            tree[now].lazy=-1;
        }
    }
    void update(int now,int l,int r,int v){
        if(tree[now].l>=l&&tree[now].r<=r){
            tree[now].sum=(tree[now].r-tree[now].l+1)*v;
            tree[now].lazy=v;
            return;
        }
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        if(l<=mid) update(now<<1,l,r,v);
        if(r>mid) update(now<<1|1,l,r,v);
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    }
    int query(int now,int l,int r){
        if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum;
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        int val=0;
        if(l<=mid) val+=query(now<<1,l,r);
        if(r>mid) val+=query(now<<1|1,l,r);
        return val;
    }
    void link1(int x,int y,int v){
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            update(1,id[top[x]],id[x],v); 
            x=fa[top[x]];
        }
        if(dep[x]<dep[y]) swap(x,y);
        update(1,id[y],id[x],v);
    }
    int link2(int x,int y){
        int ans=0;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            ans+=query(1,id[top[x]],id[x]);
            x=fa[top[x]];
        }
        if(dep[x]<dep[y]) swap(x,y);
        ans+=query(1,id[y],id[x]);
        return ans;
    }
    int main(){
        scanf("%d",&n);
        for(int i=2;i<=n;i++){
            scanf("%d",&a[i]);
            add(i,a[i]+1);
            add(a[i]+1,i);
        }
        dfs1(1,0);
        dfs2(1,1);
        build(1,1,n);
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
            scanf("%s",opt);
            scanf("%d",&x);
            x++;
            if(opt[0]=='i'){
                int ans1=link2(1,x);
                link1(1,x,1);
                int ans2=link2(1,x);
                printf("%d\n",abs(ans1-ans2));
            }
            else{
                int ans1=query(1,id[x],id[x]+size[x]-1);
                update(1,id[x],id[x]+size[x]-1,0);
                int ans2=query(1,id[x],id[x]+size[x]-1);
                printf("%d\n",abs(ans1-ans2));
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11346194.html

[Link 1]: https://www.luogu.org/problem/P2146
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/02079c4241bd4858a1c7095528833edc.png