[UOJ] #128. 【NOI2015】软件包管理器

#128. 【NOI2015】软件包管理器

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

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

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

输入格式

输入文件的第 11 行包含 11 个正整数 nn，表示软件包的总数。软件包从 00 开始编号。

随后一行包含 n−1n−1 个整数，相邻整数之间用单个空格隔开，分别表示 1,2,3,…,n−2,n−11,2,3,…,n−2,n−1 号软件包依赖的软件包的编号。

接下来一行包含 11 个正整数 qq，表示询问的总数。

之后 qq 行，每行 11 个询问。询问分为两种：

  • install xx：表示安装软件包 xx
  • uninstall xx：表示卸载软件包 xx

你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出格式

输出文件包括 qq 行。

输出文件的第 ii 行输出 11 个整数，为第 ii 步操作中改变安装状态的软件包数。

样例一

input

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

output

3
1
3
2
3

explanation

一开始所有的软件包都处于未安装状态。

安装 55 号软件包，需要安装 0,1,50,1,5 三个软件包。

之后安装 66 号软件包，只需要安装 66 号软件包。此时安装了 0,1,5,60,1,5,6 四个软件包。

卸载 11 号软件包需要卸载 1,5,61,5,6 三个软件包。此时只有 00 号软件包还处于安装状态。

之后安装 44 号软件包，需要安装 1,41,4 两个软件包。此时 0,1,40,1,4 处在安装状态。

最后，卸载 00 号软件包会卸载所有的软件包。

样例二

input

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

output

1
3
2
1
3
1
1
1
0
1

样例三

见样例数据下载。

限制与约定

测试点编号nn 的规模qq 的规模备注
1 n=5000n=5000 q=5000q=5000  
2
3 n=100000n=100000 q=100000q=100000 数据不包含卸载操作
4
5 n=100000n=100000 q=100000q=100000 编号为 ii 的软件包所依赖的软件包编号在 [0,i−1][0,i−1] 内均匀随机。
每次执行操作的软件包编号在 [0,n−1][0,n−1] 内均匀随机。
6
7
8
9 n=100000n=100000 q=100000q=100000  
10
11
12
13
14
15
16
17
18
19
20

时间限制：1s1s

空间限制：512MB512MB

下载

样例数据下载

分析

树链剖分+线段树

有点怀念当年用VM基Ubuntu然后装个东西还得sudo的日子qwq

显然，子节点依赖于父节点，那么 fa 数组一开始就可以确定了

然后只插入 父 -> 子 的边

这样可以避免很多判定

（不过讲真这样敲起来不习惯而且因为不习惯容易出错）

那么安装一个应用软件就是安置一条 根节点 到 当前点 的链，然后返回链上 未安装点 数

所以我就随手把查询和修改写一起了

代码

  1 #include<cstdio>
  2 #include<iostream>
  3 #define mid (L+R)/2
  4 #define lc (rt<<1)
  5 #define rc (rt<<1|1)
  6 #define maxn 1000000
  7 using namespace std;
  8 
  9 int n,TIM;
 10 int depth[maxn],siz[maxn],top[maxn],tid[maxn],eid[maxn],fa[maxn],son[maxn];
 11 
 12 struct node{
 13     int sum,lazy;
 14 }Tree[maxn*4];
 15 
 16 void maintain(int rt){ Tree[rt].sum = Tree[lc].sum + Tree[rc].sum; }
 17 
 18 void pushdown(int rt,int L,int R){
 19     if(L == R){ Tree[rt].lazy = 0; return; }
 20     switch(Tree[rt].lazy){
 21         case 1:
 22             Tree[lc].lazy = 1;
 23             Tree[rc].lazy = 1;
 24             Tree[lc].sum = mid-L+1;
 25             Tree[rc].sum = R-mid;
 26             Tree[rt].lazy = 0;
 27             break;
 28         case -1:
 29             Tree[lc].lazy = -1;
 30             Tree[rc].lazy = -1;
 31             Tree[lc].sum = 0;
 32             Tree[rc].sum = 0;
 33             Tree[rt].lazy = 0;
 34             break;
 35     }
 36 }
 37 
 38 int Ins_modify(int rt,int L,int R,int qL,int qR){
 39     pushdown(rt,L,R);
 40     if(qL <= L && R <= qR){
 41         int ans = (R-L+1)-Tree[rt].sum;
 42         Tree[rt].sum = (R-L+1);
 43         Tree[rt].lazy = 1;
 44         return ans;
 45     }else{
 46         int ans = 0;
 47         if(qL <= mid) ans += Ins_modify(lc,L,mid,qL,qR);
 48         if(qR > mid) ans += Ins_modify(rc,mid+1,R,qL,qR);
 49         maintain(rt);
 50         return ans;
 51     }
 52 }
 53 
 54 int Uni_modify(int rt,int L,int R,int qL,int qR){
 55     pushdown(rt,L,R);
 56     if(qL <= L && R <= qR){
 57         int ans = Tree[rt].sum;
 58         Tree[rt].sum = 0;
 59         Tree[rt].lazy = -1;
 60         return ans;
 61     }else{
 62         int ans = 0;
 63         if(qL <= mid) ans += Uni_modify(lc,L,mid,qL,qR);
 64         if(qR > mid) ans += Uni_modify(rc,mid+1,R,qL,qR);
 65         maintain(rt);
 66         return ans;
 67     }
 68 }
 69 
 70 void Ins(int u,int v = 1){
 71     int ans = 0;
 72     if(depth[top[u]] < depth[top[v]]) swap(u,v);
 73     while(top[u] != top[v]){
 74         ans += Ins_modify(1,1,n,tid[top[u]],tid[u]);
 75         u = fa[top[u]];
 76         if(depth[top[u]] < depth[top[v]]) swap(u,v);
 77     }if(depth[u] > depth[v]) swap(u,v);
 78     ans += Ins_modify(1,1,n,tid[u],tid[v]);
 79     printf("%d
",ans);
 80 }
 81 
 82 void Uni(int u){
 83     int ans = Uni_modify(1,1,n,tid[u],eid[u]);
 84     printf("%d
",ans);
 85 }
 86 
 87 struct edge{
 88     int from,v;
 89 }e[maxn]; int tot,first[maxn];
 90 void insert(int u,int v){ tot++; e[tot].from = first[u]; e[tot].v = v; first[u] = tot; }
 91 
 92 void dfs(int now){
 93     siz[now] = 1;
 94     for(int i = first[now];i;i = e[i].from){
 95         int v = e[i].v;
 96         depth[v] = depth[now] +1;
 97         dfs(v);
 98         siz[now] += siz[v];
 99         if(!son[now] || siz[v] > siz[son[now]])
100             son[now] = v;
101     }
102 }
103 
104 void dfs2(int now,int t){
105     tid[now] = ++TIM;
106     top[now] = t;
107     if(!son[now]){ eid[now] = TIM; return; }
108     dfs2(son[now],t);
109     for(int i = first[now];i;i = e[i].from){
110         int v = e[i].v;
111         if(v != son[now])
112             dfs2(v,v);
113     }eid[now] = TIM;
114 }
115 
116 inline void read(int &k){
117     k = 0; int t = 1; char ctr = getchar();
118     while(ctr < '0' || ctr > '9') ctr == '-'&&(t = -1),ctr = getchar();
119     while(ctr >= '0' && ctr <= '9') k = k*10+ctr-'0',ctr = getchar();
120     k *= t;
121 }
122 
123 int main(){
124     read(n);
125     for(int i = 1,cnt;i < n;i++){
126         read(cnt); insert(cnt+1,i+1); fa[i+1] = cnt+1;
127     }depth[1] = 1; dfs(1); dfs2(1,1);
128     int q,tmp;
129     char str[10] = {0};
130     read(q);
131     while(q--){
132         scanf("%s %d",str,&tmp);
133         switch(str[0]){
134             case 'i': Ins(tmp+1); break;
135             case 'u': Uni(tmp+1); break;
136         }
137     }
138     
139     return 0;
140 }
qwq我晕3D
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Chorolop/p/7648005.html