关于软件包管理器的近10条评论(全部评论)
1A淼淼 ┭┮﹏┭┮ 2023-12-09 20:48 15楼
好久没体验过写这么长的代码还能一次 AC 的感觉了QAQ upd：今天瞎翻代码的时候发现树链剖分里面的线段树修改参数传错了awa（本来应该是 $k$，我全设成 $1$ 了QAQ，现在改对了），就这还能 AC，只能说 CCF 的数据太水了叭qwq yrtiop 2022-02-07 18:21 14楼
人傻代码长，常数还巨TM大。 HT008 2018-01-06 17:28 13楼
我不仅是人傻自带大常数，而且是人傻自带冗长代码； Fisher. 2017-11-05 20:05 12楼
树剖过之，很裸 JustWB 2017-08-14 21:08 11楼
身败名裂...... AntiLeaf 2017-01-03 14:19 10楼
把x=father[top[x]]写成x=father[x]查了一下午qaq 我是傻逼qaqqqqqqqqqqqqqqqqqqqqqqqqqqqq 题解（骗访问）：http://www.cnblogs.com/JSL2018/p/5907108.html cdcq 2016-09-25 21:43 9楼
强行邀一波qaq http://sxysxy.org/blogs/36 sxysxy 2016-09-18 21:02 8楼
Fmuckss 2016-09-13 13:43 7楼
maintain会挂掉，不要用 crehs 2016-08-08 21:23 6楼

2019. [NOI 2015]软件包管理器

★★★☆ 输入文件：manager.in 输出文件：manager.out 简单对比
时间限制：1.5 s 内存限制：512 MiB

你决定设计你自己的软件包管理器。不可避免的，你要解决软件包之间的依赖关系。如果A依赖B，那么安装A之前需安装B，卸载B之前须卸载A。0号软件包不依赖任何软件包。依赖关系不存在环(包括自环)。

你的任务是，求出每次安装、删除操作会改变多少个包的状态。

安装一个已安装的软件包，或者卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0

每次操作不仅需要计算安装软件包数，还作为操作影响后来的安装/删除

第一行一个整数n,表示软件包的总数。

随后n-1个整数$a_1,a_2,...a_{n-1}$，表示第i个软件包依赖第$a_i$个软件包

接下来一行一个整数q,表示询问数

之后q行，每行一个询问，询问分为两种

install x：表示安装x

uninstall x：表示卸载x

q行，每行一个整数，为第i步操作改变安装状态的软件包数

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

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

安装5号软件包，需安装0,1,5三个软件包

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

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

之后安装4号软件包，需安装1,4两个软件包。此时0,1,4处于安装状态

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

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

1,2:n=5000 q=5000

3,4:n=100000 q=100000 没有卸载操作

5,6,7,8 n=100000,q=100000 依赖关系和操作随机

9-20 n=100000,q=100000 不随机

NOI2015Day1T2