数据结构 ·

(静态/动态)点分治 专题训练

从成都集训后几天就开始学这个,发现细节非常多,不好处理,于是暂时弃坑了,现在重新捡起来,一定要刷掉。

 

静态点分治

处理的问题主要是和树上的路径有关,且树的结构不发生改变,点权边权等也不变。大体思路就是每次找到重心,处理过重心的路径并统计答案,递归进入子树。很多问题都涉及到要删除重复计数的影响,非常麻烦,而且个人感觉比较容易出错,于是就比较常用另一种思路:同样是找重心并处理过重心的路径,但是遍历每颗子树时,将答案和其他已经遍历过的子树答案进行合并,可能会用到一些数据结构,之后再合并信息,处理下一颗子树。这样的优点是不会出现重复计数,而且个人感觉细节较少。

BZOJ 2152 聪聪可可

求长度是3的倍数的路径条数。做这道题时采用的是第一种思路,即统计完成后去除重复的,调了很久,还看了题解,感觉自己十分不喜欢这种思路。

 

BZOJ 2599 [IOI2011]Race

求一条边权值和为k的路径经过的最小边数。

采用的第二种思路,每次合并子树。开个桶,记录由当前根到每种距离的最小深度,每次合并即可,非常好理解,但是这道题细节同样很多,这应该是点分的通性吧。

 

COGS 2155 免费旅行II

有黑白两种点,求经过黑点数不超过k的路径最大长度。因为这道题的限制是不超过k,所以单单开一个桶貌似不太可行了。题解貌似很麻烦,所以我用数据结构来做。上个树状数组,保存经过黑点数限制下的最大长度,就基本上和上一题一样了。树状数组可以直接时间戳实现O(1)清空,总时间复杂度O(nlog^2n)。

 

BZOJ 1468 tree

统计距离<=k的点对数。正解同样是奇技淫巧,统计完子树后排序+单调指针,还是要去除重复元素,所以我依旧用数据结构来代替。开一个treap,保存已经遍历过的子树中到各点的距离,然后在遍历新树的时候直接查rank即可,时间复杂度和正解一致O(nlog^2n)。尽管使用了带旋转treap卡常,跑的还是比别人慢了40ms。

 


动态点分治

可以解决更多问题,比如涉及单点的修改、子树查询等,支持强制在线。具体做法是先跑出来原树的重心,在重心间连边,建出一颗新树,新树的深度显然是O(logn)的,所以很多修改查询操作的时间复杂度可以得到保障。我们可以利用子树信息对父亲的影响来分治并统计答案。

BZOJ 3924 [Zjoi2015]幻想乡战略游戏

单点修改点权,查询树上最小的$$\sum_{i=1}^{n} dis(u,i)*d(u)$$

先考虑如何快速求出每个点的加权距离和。对于每个点,保存子树节点到当前点、分治父亲的加权距离,以及子树权值和。暴力向上跳,删除重复计数的部分即可,感觉还是躲不开各种细节啊。至于找点,还不太会,因为暴力可过所以就直接暴力跳,理论是可以卡成O(n)的,当成坑留着吧。

 

BZOJ 4372 烁烁的游戏

给距离某点小于等于定值的点权加,单点查询点权。

做之前感觉想不出来啥,做完这道题之后才明白了动态点分的套路。主要就是通过记录O(logn)级别的信息,完成修改操作对整棵树的影响,同时以同样的复杂度进行查询操作,但前提是子树对分治爹的影响可以比较容易地消除。

对于这道题,可以对于每个点开两个线段树,一个记录分治子树中各个距离的点权变化量,另一个记录分治子树的点与分治爹各个距离的点权变化量。如果存在分治爹,就将当前子树对答案的贡献中减去对分治爹的贡献,这样就可以防止重复计数了。

 

BZOJ 3730 振波

单点修改点权,查询距离小于定值的点权和。和上一道题思路一样,但是就是被卡常了。。。

 

BZOJ 4012 [HNOI2015]开店

边、点各有权值,不带修改,每次要求查询点权在[L,R]内的点到当前点距离之和。

同样是套路,一开始想了一个对每个点开无旋treap,以点权为关键字,维护子树距离和,每次提取区间即可。空间、时间都是O(nlog^2n),目测可过就开始写。但是刚写了一点,就发现这道题根本不涉及修改,直接把点权距离进行排序后二分即可,复杂度应该是一样的,但是常数一定很小。

最后写完一测,跑了接近60s,那么我的无旋treap做法就很有可能被卡常了。。。给了我一个教训,不要上来就想用高级数据结构来解决问题,虽然很多时候是可行的,但是在更多的情况下会以时间效率或代码难度上造成障碍。

 

参与评论