BZOJ_4196_[Noi2015]软件包管理器_树链剖分

BZOJ_4196_[Noi2015]软件包管理器_树链剖分

题意：

Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,…,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，Am−1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

分析：裸树剖吼啊。

线段树维护个区间和。

安装为1，卸载为0。

代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
#define ls p<<1
#define rs p<<1|1
int head[N],to[N<<1],nxt[N<<1],cnt,n,tot,q;
int dep[N],son[N],siz[N],fa[N],idx[N],top[N];
int t[N<<2],lz[N<<2];
char ch[10];
void read(int &x){
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
    x*=f;
}
inline void add(int u,int v){
    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs1(int x){
    siz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        if(to[i]!=fa[x]){
            fa[to[i]]=x;
            dep[to[i]]=dep[x]+1;
            dfs1(to[i]);
            siz[x]+=siz[to[i]];
            if(siz[to[i]]>siz[son[x]])son[x]=to[i];
        }
    }
}
void dfs2(int x,int t){
    top[x]=t;idx[x]=++tot;
    if(son[x])dfs2(son[x],t);
    for(int i=head[x];i;i=nxt[i]){
        if(to[i]!=fa[x]&&to[i]!=son[x])dfs2(to[i],to[i]);
    }
}
void pud(int l,int r,int p){
    if(lz[p]==0)return ;
    lz[ls]=lz[p];lz[rs]=lz[p];
    int mid=l+r>>1;
    t[ls]=(lz[p]-1)*(mid-l+1);
    t[rs]=(lz[p]-1)*(r-mid);
    lz[p]=0;
}
void up(int l,int r,int x,int y,int p,bool flg){
    if(x<=l&&r<=y){
        lz[p]=flg+1;
        t[p]=flg*(r-l+1);return ;
    }
    int mid=l+r>>1;
    pud(l,r,p);
    if(x<=mid)up(l,mid,x,y,ls,flg);
    if(y>mid)up(mid+1,r,x,y,rs,flg);
    t[p]=t[ls]+t[rs];
}
int query(int l,int r,int x,int y,int p,bool flg){
    if(x<=l&&r<=y){
        return flg?t[p]:(r-l+1-t[p]);
    }
    int re=0,mid=l+r>>1;
    pud(l,r,p);
    if(x<=mid)re+=query(l,mid,x,y,ls,flg);
    if(y>mid)re+=query(mid+1,r,x,y,rs,flg);
    return re;
}
int main(){
    read(n);
    int x;
    for(int i=1;i<n;i++){
        read(x);add(x+1,i+1);add(i+1,x+1);
    }
    dfs1(1);dfs2(1,1);
    read(q);
    while(q--){
        scanf("%s%d",ch,&x);
        x++;
        if(ch[0]=='i'){
            int y=1,ans=0;
            while(top[x]!=top[y]){
                if(dep[top[x]]>dep[top[y]])swap(x,y);
                ans+=query(1,n,idx[top[y]],idx[y],1,0);
                up(1,n,idx[top[y]],idx[y],1,1);
                y=fa[top[y]];
            }if(dep[x]<dep[y])swap(x,y);
            ans+=query(1,n,idx[y],idx[x],1,0);
            up(1,n,idx[y],idx[x],1,1);
            printf("%d\n",ans);
        }else{
            printf("%d\n",query(1,n,idx[x],idx[x]+siz[x]-1,1,1));
            up(1,n,idx[x],idx[x]+siz[x]-1,1,0);
        }
    }
}