【JZOJ5730】【luoguP2146】【Comet OJC0396】软件包管理器
descriptionLinux用户和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,……,A[m-1]依赖Am,而Am依赖A1,则称这m个软件包的依赖关系构成环),当然也不会有一个软件包依赖自己。 现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包),你的任务就是实现这个部分。注意,安装一个已安装的软件包,或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况下,改变安装状态的软件包数为0。 analysis
code#pragma GCC optimize("O3") #pragma G++ optimize("O3") #include<stdio.h> #include<string.h> #define MAXN 100005 #define ll long long #define reg register ll #define fo(i,a,b) for (reg i=a;i<=b;++i) #define fd(i,b) for (reg i=a;i>=b;--i) #define rep(i,a) for (reg i=last[a];i;i=next[i]) using namespace std; ll last[MAXN],next[MAXN],tov[MAXN]; ll fa[MAXN],top[MAXN],size[MAXN],depth[MAXN],heavy_son[MAXN]; ll tr[MAXN<<2],bz[MAXN<<2],to_tree[MAXN],to_num[MAXN]; ll n,q,tot; char s[10]; inline ll read() { ll x=0,f=1;char ch=getchar(); while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();} while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f; } inline ll abs(ll x){return x>0?x:-x;} inline void link(ll x,ll y){next[++tot]=last[x],last[x]=tot,tov[tot]=y;} inline void dfs1(ll x) { rep(i,x) { depth[tov[i]]=depth[x]+1,size[tov[i]]=1,dfs1(tov[i]),size[x]+=size[tov[i]]; if (size[tov[i]]>size[heavy_son[x]])heavy_son[x]=tov[i]; } } inline void dfs2(ll x,ll y) { if (!x)return;top[x]=y; to_tree[x]=++tot,to_num[tot]=x,dfs2(heavy_son[x],y); rep(i,x)if (tov[i]!=heavy_son[x])dfs2(tov[i],tov[i]); } inline void maketree(ll t,ll l,ll r) { bz[t]=-1;if (l==r)return; ll mid=(l+r)>>1;maketree(t<<1,l,mid),maketree((t<<1)+1,mid+1,r); } inline void downdata(ll t,ll r) { if (bz[t]==-1)return;ll mid=(l+r)>>1; tr[t<<1]=(mid-l+1)*bz[t],tr[(t<<1)+1]=(r-mid)*bz[t]; bz[t<<1]=bz[(t<<1)+1]=bz[t],bz[t]=-1; } inline void tree_modify(ll t,ll r,ll x,ll y,ll z) { if (l==x && y==r){tr[t]=(r-l+1)*z,bz[t]=z;return;} ll mid=(l+r)>>1;downdata(t,r); if (y<=mid)tree_modify(t<<1,mid,x,y,z); else if (x>mid)tree_modify((t<<1)+1,r,z); else tree_modify(t<<1,z),tree_modify((t<<1)+1,z); tr[t]=tr[t<<1]+tr[(t<<1)+1]; } inline void modify(ll x) { while (top[x]!=1)tree_modify(1,1,n,to_tree[top[x]],to_tree[x],1),x=fa[top[x]]; tree_modify(1,1); } int main() { //freopen("P2146.in","r",stdin); freopen("manager.in",stdin); freopen("manager.out","w",stdout); n=read();fo(i,2,n)link(fa[i]=read()+1,i); tot=0,dfs1(depth[1]=size[1]=1),dfs2(1,maketree(1,n),q=read(); while (q--) { scanf("%s",&s);ll x=read()+1,tmp=tr[1]; if (s[0]=='i') { modify(x),printf("%lldn",abs(tr[1]-tmp)); continue; } tree_modify(1,to_tree[x]+size[x]-1,0); printf("%lldn",abs(tr[1]-tmp)); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |