(luogu2146)软件包管理器(NOI2015) 发表于 2018-02-04 | 分类于 solution , 树相关 , 树链剖分 树链剖分笔记索引 思路:一样的是树链剖分+线段树 不同的是这个线段树和之前那道有所不同 每个区间记录区间内已安装的安装包数量, 这样操作就简单了 代码:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161#include <iostream>#include <cstdio>#include <cctype>using namespace std;const int Mn(100005);int qrd() //快读{ int x(0); char c(getchar()); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } return x;}int n;char opr[20]; //读入用字符串struct edge //一样的边表{ int e,nt;}ed[Mn<<1];int vs[Mn],ec(0);void adde(int s,int e){ ed[++ec].e=e; ed[ec].nt=vs[s]; vs[s]=ec;}int dp[Mn],pa[Mn],sz[Mn],hs[Mn]; //还是一样的操作void dfs1(int x){ sz[x]=1; for(int e(vs[x]);e;e=ed[e].nt) { int& ntn(ed[e].e); if(!dp[ntn]) { dp[ntn]=dp[x]+1; dfs1(ntn); sz[x] += sz[ntn]; if(sz[hs[x]]<sz[ntn]) hs[x]=ntn; } }}int tp[Mn],vp[Mn],dc(0);void dfs2(int x){ vp[x] = ++dc; if(hs[x]) { tp[hs[x]]=tp[x]; dfs2(hs[x]); } for(int e(vs[x]);e;e=ed[e].nt) { int& ntn(ed[e].e); if(dp[ntn]>dp[x] && ntn!=hs[x]) { tp[ntn] = ntn; dfs2(ntn); } }}struct sn // 线段树结点{ int l,r,n1,t; // 左端点, 右端点, 已安装数量, 懒标记}t[Mn<<2];void bud(int l,int r,int rt=1) //建树{ sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]); nd.t=-1; if(l==r) { nd.l=nd.r=l; nd.n1=0; } else { int mid((l+r)>>1); bud(l,mid,rt<<1); bud(mid+1,r,rt<<1|1); nd.l=l, nd.r=r; nd.n1=0; }}void pd(int rt) // 下放标记{ sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]); if(nd.t!=-1) { ls.t=rs.t=nd.t; ls.n1 = (nd.t ? (ls.r-ls.l+1) : 0); //将左右儿子全部置1 rs.n1 = (nd.t ? (rs.r-rs.l+1) : 0); nd.t = -1; }}int ist(int ml,int mr,int rt=1) //安装{ sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]); int ret(0); if(nd.l>=ml && nd.r<=mr) //全部置1并打上标记 { ret = (nd.r-nd.l+1)-nd.n1; //记录该区间状态修改数 nd.n1 = nd.r-nd.l+1; nd.t = 1; } else { pd(rt); if(ml<=ls.r) ret+=ist(ml,mr,rt<<1); if(mr>=rs.l) ret+=ist(ml,mr,rt<<1|1); nd.n1 = ls.n1+rs.n1; } return ret;}int dlt(int ml,int mr,int rt=1) //删除{ sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]); int ret(0); if(nd.l>=ml && nd.r<=mr) //全部置0 { ret = nd.n1; //记录该区间状态修改数 nd.n1 = 0; nd.t = 0; } else { pd(rt); if(ml<=ls.r) ret+=dlt(ml,mr,rt<<1); if(mr>=rs.l) ret+=dlt(ml,mr,rt<<1|1); nd.n1 = ls.n1+rs.n1; } return ret;}int main(){ cin >> n; for(int i(2);i<=n;++i) { int p(qrd()); pa[i] = p+1; adde(p+1,i), adde(i,p+1); } dp[1]=1; dfs1(1); tp[1]=1; dfs2(1); bud(1,n); int q(qrd()); while(q--) { scanf("%s",opr); int x(qrd()); ++x; if(opr[0]=='i') //安装, 从需安装安装包到根结点的所有安装包全部安装 { int ans(0); while(x) { ans += ist(vp[tp[x]],vp[x]); x = pa[tp[x]]; } printf("%d\n",ans); } else if(opr[0]=='u') //删除, 把子树中的安装包全部删除 printf("%d\n",dlt(vp[x],vp[x]+sz[x]-1)); } return 0;}