「NOI2015」软件包管理器-树链剖分
· ✏️ 1215 words · ☕ 3 mins read
你决定设计你自己的软件包管理器。如果软件包 A 依赖软件包 B ,那么安装软件包 A 以前,必须先安装软件包 B 。同时,如果想要卸载软件包 B ,则必须卸载软件包 A 。现在你已经获得了所有的软件包之间的依赖关系。除
现在有一些安装或卸载软件包的操作,需要求出这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包)。
你决定设计你自己的软件包管理器。如果软件包 A 依赖软件包 B ,那么安装软件包 A 以前,必须先安装软件包 B 。同时,如果想要卸载软件包 B ,则必须卸载软件包 A 。现在你已经获得了所有的软件包之间的依赖关系。除
现在有一些安装或卸载软件包的操作,需要求出这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包)。
给定一个字符串
特别地,为了避免大量的输出,你不需要输出
维护一个数列,给定初始的
现有六种命令:
初始时,第
有两种指令:
合并指令为 M i j
,含义为将第
询问指令为 C i j
。该指令意思询问第
维护一个数列。
现有四种命令,新加入一个数
如果新加入的数