【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，……，A[m-1]依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

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

n,q<=1e5

分析

显然的树剖，安装了的标记为1，未安装标记为0，求出一段区间的和相当于求出了安装的数量。

对于install 求出x点到根的和，再全部区间更新为1

对于uninstall 求出子树的和，再更新整棵子树为0，因此Lazy标记不能初始为0，初始化为-1

需要注意的是，线段树此处应该是区间覆盖，毕竟你的标记是直接互相覆盖了的。

只需将所有的“+=”改为“=”，这样就实现了区间覆盖。

代码

  1. #include<bits/stdc++.h>  
  2. using namespace std;  
  3. #define N 100010  
  4. #define lc (p<<1)  
  5. #define rc (p<<1|1)  
  6. #define mid (t[p].l+t[p].r>>1)  
  7. char s[N];  
  8. int n,q,cnt,idx;  
  9. int d[N],f[N],id[N],top[N],son[N],siz[N],first[N];  
  10. struct email  
  11. {  
  12.     int u,v;  
  13.     int nxt;  
  14. }e[N*4];  
  15. struct tree  
  16. {  
  17.     int l,r,sum,lazy;  
  18. }t[N*4];  
  19. inline void add(int u,int v)  
  20. {  
  21.     e[++cnt].nxt=first[u];first[u]=cnt;  
  22.     e[cnt].u=u;e[cnt].v=v;  
  23. }  
  24. inline void pushup(int p)  
  25. {  
  26.     t[p].sum=t[lc].sum+t[rc].sum;  
  27. }  
  28. inline void pushnow(int p,int v)  
  29. {  
  30.     t[p].sum=(t[p].r-t[p].l+1)*v;  
  31.     t[p].lazy=v;  
  32. }  
  33. inline void pushdown(int p)  
  34. {  
  35.     if(t[p].lazy!=-1)  
  36.     {  
  37.         pushnow(lc,t[p].lazy);  
  38.         pushnow(rc,t[p].lazy);  
  39.         t[p].lazy=-1;  
  40.     }  
  41. }  
  42.   
  43. inline void build(int p,int l,int r)  
  44. {  
  45.     t[p].l=l;t[p].r=r;t[p].lazy=-1;  
  46.     if(l==r)return ;  
  47.     int bm=l+r>>1;  
  48.     build(lc,l,bm);build(rc,bm+1,r);  
  49.     pushup(p);  
  50. }  
  51.   
  52. inline void update(int p,int ql,int qr,int v)  
  53. {  
  54.     if(ql<=t[p].l&&qr>=t[p].r)  
  55.     {  
  56.         pushnow(p,v);  
  57.         return ;  
  58.     }  
  59.     pushdown(p);  
  60.     if(ql<=mid)update(lc,ql,qr,v);  
  61.     if(qr>mid)update(rc,ql,qr,v);  
  62.     pushup(p);   
  63. }  
  64.   
  65. inline int query(int p,int ql,int qr)  
  66. {  
  67.     int ret=0;  
  68.     if(ql<=t[p].l&&qr>=t[p].r)return t[p].sum;  
  69.     pushdown(p);  
  70.     if(ql<=mid)ret+=query(lc,ql,qr);  
  71.     if(qr>mid)ret+=query(rc,ql,qr);  
  72.     return ret;  
  73. }  
  74.   
  75. inline void dfs1(int u,int fa,int dep)  
  76. {  
  77.     f[u]=fa;siz[u]=1;d[u]=dep;  
  78.     for(int i=first[u];i;i=e[i].nxt)  
  79.     {  
  80.         int v=e[i].v;  
  81.         if(v==fa)continue;  
  82.         dfs1(v,u,dep+1);  
  83.         siz[u]+=siz[v];  
  84.         if(siz[v]>siz[son[u]]||son[u]==0)  
  85.             son[u]=v;  
  86.     }  
  87. }  
  88.   
  89. inline void dfs2(int u,int t)  
  90. {  
  91.     top[u]=t;id[u]=++idx;  
  92.     if(!son[u])return;  
  93.     dfs2(son[u],t);  
  94.     for(int i=first[u];i;i=e[i].nxt)  
  95.     {  
  96.         int v=e[i].v;  
  97.         if(v!=f[u]&&v!=son[u])  
  98.             dfs2(v,v);  
  99.     }  
  100. }  
  101.   
  102. inline int asktree(int x)  
  103. {  
  104.     int ret=0,fx=top[x];  
  105.     while(fx)  
  106.     {  
  107.         ret+=id[x]-id[fx]+1-query(1,id[fx],id[x]);  
  108.         update(1,id[fx],id[x],1);  
  109.         x=f[fx];fx=top[x];  
  110.     }  
  111.     ret+=id[x]-id[0]+1-query(1,id[0],id[x]);  
  112.     update(1,id[0],id[x],1);  
  113.     return ret;  
  114. }  
  115.   
  116. int main()  
  117. {  
  118.     scanf("%d",&n);  
  119.     for(int u=1;u<n;u++)  
  120.     {  
  121.         int v;  
  122.         scanf("%d",&v);  
  123.         add(u,v);add(v,u);  
  124.     }  
  125.     dfs1(0,0,1);dfs2(0,0);build(1,1,n);  
  126.     scanf("%d",&q);  
  127.     for(int i=1;i<=q;i++)  
  128.     {  
  129.         int x;  
  130.         scanf("%s%d",s,&x);  
  131.         if(s[0]=='i')printf("%d ",asktree(x));  
  132.         else  
  133.         {  
  134.             printf("%d ",query(1,id[x],id[x]+siz[x]-1));  
  135.             update(1,id[x],id[x]+siz[x]-1,0);  
  136.         }  
  137.     }  
  138.     return 0;  
  139. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/NSD-email0820/p/9832611.html