[NOI2015]软件包管理器[树链剖分,线段树]

题面

毒瘤数据结构复习系列.

设0为未安装, 1为已安装, 当安装某个包x时, 统计root~x路径上0的个数, 再把整条路径设为1

卸载包x时, 统计x为根的子树1的个数, 再把整颗子树设为0

线段树的区间覆盖只要把懒标记的+=改为=就行了

看到题解中还有一种更妙的做法: 只进行update操作, 统计线段树根节点sum值变化即可, 理论上常数是我的一半(妙啊)

赞(0)
大部分原创, 转载请附上原文链接. 侵删:CGaZn的博客 » [NOI2015]软件包管理器[树链剖分,线段树]

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址