首页 » C++ » bzoj4196 [Noi2015] 软件包管理器 树链剖分

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

原文 http://blog.csdn.net/jpwang8/article/details/79052391

2018-01-14 02:00:33阅读(161)

Description

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。

n=100000
q=100000

Solution

install操作就用0到x中节点数减去1的数量然后区间修改
uninstall就直接在子树里面搞
一开始还二分找一个距离x最近的没有安装的父亲,结果贼慢,果然洛谷神姬

Code
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define fill(x,t) memset(x,t,sizeof(x))
using std:: swap;
const int N=400005;
const int E=1600005;
struct edge{int x,y,next;}e[E];
int size[N],pos[N],dep[N],fa[N],bl[N],a[N];
int sum[N<<2],num[N<<2],lazy[N<<2];
int ls[N],edCnt,n,m;
int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}
void addEdge(int x,int y) {
    e[++edCnt]=(edge){x,y,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge){y,x,ls[y]}; ls[y]=edCnt;
}
void dfs1(int now) {
    size[now]=1;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa[now]) continue;
        dep[e[i].y]=dep[now]+1;
        fa[e[i].y]=now;
        dfs1(e[i].y);
        size[now]+=size[e[i].y];
    }
}
void dfs2(int now,int up) {
    pos[now]=++pos[0]; bl[now]=up;
    int mx=0;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa[now]||size[e[i].y]<=size[mx]) continue;
        mx=e[i].y;
    }
    if (!mx) return ;
    dfs2(mx,up);
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa[now]||e[i].y==mx) continue;
        dfs2(e[i].y,e[i].y);
    }
}
void push_down(int now,int tl,int tr) {
    if (lazy[now]==-1) return ;
    int mid=(tl+tr)>>1;
    lazy[now<<1]=lazy[now<<1|1]=lazy[now];
    num[now<<1]=num[now<<1|1]=lazy[now];
    sum[now<<1]=(mid-tl+1)*lazy[now];
    sum[now<<1|1]=(tr-mid)*lazy[now];
    lazy[now]=-1;
}
int query(int now,int tl,int tr,int l,int r) {
    if (tl==l&&tr==r) return sum[now];
    push_down(now,tl,tr);
    int mid=(tl+tr)>>1;
    if (r<=mid) return query(now<<1,tl,mid,l,r);
    else if (l>mid) return query(now<<1|1,mid+1,tr,l,r);
    else return query(now<<1,tl,mid,l,mid)+query(now<<1|1,mid+1,tr,mid+1,r);
}
void modify(int now,int tl,int tr,int l,int r,int v) {
    if (tl==l&&tr==r) {
        num[now]=v;
        sum[now]=(tr-tl+1)*v;
        lazy[now]=v;
        return ;
    }
    push_down(now,tl,tr);
    int mid=(tl+tr)>>1;
    if (r<=mid) modify(now<<1,tl,mid,l,r,v);
    else if (l>mid) modify(now<<1|1,mid+1,tr,l,r,v);
    else {
        modify(now<<1,tl,mid,l,mid,v);
        modify(now<<1|1,mid+1,tr,mid+1,r,v);
    }
    sum[now]=sum[now<<1]+sum[now<<1|1];
    if (num[now<<1]==num[now<<1|1]) num[now]=num[now<<1];
    else num[now]=-1;
}
void buildTree(int now,int tl,int tr) {
    lazy[now]=-1;
    if (tl==tr) return ;
    int mid=(tl+tr)>>1;
    buildTree(now<<1,tl,mid);
    buildTree(now<<1|1,mid+1,tr);
}
void change(int x,int y,int v) {
    while (bl[x]!=bl[y]) {
        if (dep[bl[x]]<dep[bl[y]]) swap(x,y);
        modify(1,1,n,pos[bl[x]],pos[x],v);
        x=fa[bl[x]];
    }
    if (pos[x]>pos[y]) swap(x,y);
    modify(1,1,n,pos[x],pos[y],v);
}
int get_sum(int x,int y) {
    int ret=0;
    while (bl[x]!=bl[y]) {
        if (dep[bl[x]]<dep[bl[y]]) swap(x,y);
        ret+=query(1,1,n,pos[bl[x]],pos[x]);
        x=fa[bl[x]];
    }
    if (pos[x]>pos[y]) swap(x,y);
    ret+=query(1,1,n,pos[x],pos[y]);
    return ret;
}
int main(void) {
    scanf("%d",&n);
    buildTree(1,1,n);
    rep(i,2,n) {
        int x; scanf("%d",&x); x++;
        addEdge(i,x);
    }
    dep[1]=1; dfs1(1); dfs2(1,1);
    scanf("%d",&m);
    while (m--) {
        char opt[10]; scanf("%s",opt);
        int x; scanf("%d",&x); x++;
        if (opt[0]=='i') {
            printf("%d\n", dep[x]-get_sum(1,x));
            change(1,x,1);
        } else if (opt[0]=='u') {
            printf("%d\n", query(1,1,n,pos[x],pos[x]+size[x]-1));
            modify(1,1,n,pos[x],pos[x]+size[x]-1,0);
        }
    }
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹