bzoj3531

题目链接

树剖+动态开点线段树

题解

啥玩意开\(n\)颗线段树,这么牛逼?

这不是\(RE\)成\(mmp\)??

还有动态开点???


宗教数量只有\(10^5\),我们对于给定的边可以先树剖,因为操作中有\(CC\ x\ c\)表示城市\(x\)的居民全部改信\(c\)教,对于这个我们需要先将城市\(x\)的信仰重置,然后再改信教.

因为信仰不同,所以我们需要针对每一种信仰开一颗线段树.

而且线段树是动态开点,如果每一颗线段树都要建成满二叉树的话,是没有空间的,我们每次使用到一个节点就新建一个节点,暂时没写内存回收的…因为不会啊摔

对于树剖跳着找宗教的.要注意,当\(l\)改变了,\(c[x]\)也一定会变,然而线段树并不会变,所以我们需要记录\(x\)最初的线段树的根节点.

即\(work\)函数里面的\(oo\)

不能每次都用\(root[c[l]]\)!!!!!!

其他就是基础的单点修改和区间查询喽.


By:Wahacer

2017.12.25

17:34

发表评论

电子邮件地址不会被公开。 必填项已用*标注