bzoj4196: [Noi2015]软件包管理器

106 阅读 0 评论 70 点赞

我是靠谱客的博主完美哈密瓜，最近开发中收集的这篇文章主要介绍bzoj4196: [Noi2015]软件包管理器，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=4196

思路：裸裸的树链剖分。设已安装的为1，未安装的为0。

对于安装操作，就是询问x到0的路径上0的个数，然后把这个路径赋为1

对于卸载操作，就是询问x的子树中1的个数，然后把子树赋为0。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((l+r)>>1)
const int maxn=200010,maxt=maxn<<2;
using namespace std;
int n,Q,last[maxn],pre[maxn],now[maxn],son[maxn],tot,a[maxn],cnt,w[maxn],size[maxn],hson[maxn],top[maxn],fa[maxn],dep[maxn];
char op[12];
 
struct Tree{
    int sum[maxt],cov[maxt],size[maxt];
    void down(int p){
        if (cov[p]!=-1){
            sum[ls]=size[ls]*cov[p],sum[rs]=size[rs]*cov[p];
            cov[ls]=cov[rs]=cov[p],cov[p]=-1;
        }
    }
    void build(int p,int l,int r){
        if (l==r){sum[p]=0,cov[p]=-1,size[p]=1;return;}
        build(ls,l,mid),build(rs,mid+1,r);
        sum[p]=sum[ls]+sum[rs],size[p]=size[ls]+size[rs];
    }
    void change(int p,int l,int r,int a,int b,int v){
        if (l==a&&r==b){sum[p]=v*size[p],cov[p]=v;return;}
        down(p);
        if (b<=mid) change(ls,l,mid,a,b,v);
        else if (a>mid) change(rs,mid+1,r,a,b,v);
        else change(ls,l,mid,a,mid,v),change(rs,mid+1,r,mid+1,b,v);
        sum[p]=sum[ls]+sum[rs];
    }
    int query(int p,int l,int r,int a,int b){
        if (l==a&&r==b){return sum[p];}
        down(p);
        if (b<=mid) return query(ls,l,mid,a,b);
        else if (a>mid) return query(rs,mid+1,r,a,b);
        else return query(ls,l,mid,a,mid)+query(rs,mid+1,r,mid+1,b);
    }
}Seg;
 
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
void dfs(int x){
    size[x]=1;
    for (int y=now[x];y;y=pre[y])
        if (son[y]!=fa[x]){
            fa[son[y]]=x,dep[son[y]]=dep[x]+1;
            dfs(son[y]),size[x]+=size[son[y]];
            if (size[son[y]]>size[hson[x]]) hson[x]=son[y];
        }
}
 
void btree(int x,int tp){
    w[x]=++cnt,a[cnt]=0,top[x]=tp;
    if (hson[x]) btree(hson[x],tp);
    for (int y=now[x];y;y=pre[y])
        if (son[y]!=fa[x]&&son[y]!=hson[x])
            btree(son[y],son[y]);
    last[x]=cnt;
}
 
void answer(int a,int b){
    int f1=top[a],f2=top[b],sum=0,num=dep[b]-dep[a]+1;
    while (f1!=f2){
        if (dep[f1]<dep[f2]) swap(f1,f2),swap(a,b);
        //printf("sum%d %d %dn",sum,f1,a);
        sum+=Seg.query(1,1,n,w[f1],w[a]);
         
        Seg.change(1,1,n,w[f1],w[a],1);
        //puts("fuck");
        a=fa[f1],f1=top[a];
    }
    if (dep[a]>dep[b]) swap(a,b);
    sum+=Seg.query(1,1,n,w[a],w[b]);
   // printf("%d %dn",num,sum);
    Seg.change(1,1,n,w[a],w[b],1);
    printf("%dn",num-sum);
}
 
int main(){
    scanf("%d",&n);
    for (int i=2,x;i<=n;i++) scanf("%d",&x),x++,add(x,i);
    dfs(1),btree(1,1),Seg.build(1,1,n);
    //for (int i=1;i<=n;i++) printf("%d %dn",w[i],last[i]);
    scanf("%d",&Q);
    for (int i=1,x;i<=Q;i++){
        scanf("%s%d",op,&x),x++;
        if (op[0]=='i') answer(1,x);
        else{
            printf("%dn",Seg.query(1,1,n,w[x],last[x]));
            Seg.change(1,1,n,w[x],last[x],0);
        }
    }
    return 0;
}