点分治&cdq分治

# 点分治 ## 前置芝士 [树的重心](https://oi-wiki.org/graph/tree-centroid/) [树分治](https://oi-wiki.org/graph/tree-divide/) ## 例题略解 #### [P3806 【模板】点分治1](https://www.luogu.com.cn/problem/P3806) 板子题，先暴力找到整棵树的重心，然后先求出重心到各点的距离，进而算出他所在树的各个节点的距离，在对应的ans数组加一;然后再接着扫子节点，并把儿子节点子树的贡献减去，最后回答询问。 然后我们愉快的$TLE60pts$,题目上也有说明，这种做法使用于大部分不过本体比较卡时间，储存然后离线剪枝就好了。 这里给出$60pts$的[$code$](https://www.luogu.com.cn/paste/71vzq9l7) #### [P2634 [国家集训队]聪聪可可](https://www.luogu.com.cn/problem/P2634) luogu的数据有那么**亿点**水，我点分治打假了（find函数x打成了i，Divide函数to打成了x）都没事。。。 和上一题差不多，就是存储不同，对于mod3不同的余数进行储存，然后给自己加一个$p_0^2+2\times p_1\times p_2$扫到儿子再减去儿子的这个值就好了 [$code$](https://www.luogu.com.cn/paste/5eexl1r1) #### [P4149 [IOI2011]Race](https://www.luogu.com.cn/problem/P4149) 乍一看这不上面的模板题嘛，然后愉快的WA0pts。 这个题不一样的一点就是维护距离的同时还需要再维护一个边数，还是和前面的题一样，整一个桶储存更新，然后对于距离大于k的剪枝,再注意一下桶的数组大小。 还有就是solve函数里记得跳过访问过的节点 ~~（别问我为啥知道，TLE90挺好的）~~ [$code$](https://www.luogu.com.cn/paste/xp9klttq) #### [P4178 Tree](https://www.luogu.com.cn/problem/P4178) 看着是个板子题，其实不然。。 讲了点分治的一种新方法（至少我没听过）**染色法**。 大概就是把每一棵搜到的子树标记上一种颜色，然后对于想要求的一棵子树根据dis由小到大排序后压入双段队列 ~~（队列好像本来就是双端的）~~，然后一个一个弹出来，更新就行了。 [$code$](https://www.luogu.com.cn/paste/30bnrqz3) #### [U164635 [BZOJ3697]采药人的路径](https://www.luogu.com.cn/problem/U164635) 思路有一点妙，先是把阴也就是边权为0的边化为-1。我们求出每个结点到根节点的路径和dis，如果这条路径上有两个结点的dis相等,就说明有一段的路径和为0，即这个路径上可以设置一个休息站。 然后开一个$f[i][0/1]$和一个$g[i][0/1]$分别表示dis为i的正在运算子树和其他子树是否可以建休息站。对于下标为负数的情况直接给所有下标都加上一个n就好了。 [$code$](https://www.luogu.com.cn/paste/ykjcnxck) #### [P3714 [BJOI2017]树的难题](https://www.luogu.com.cn/problem/P3714) 单调队列优化的[比较好的题解](https://ctz45562.github.io/2019/08/15/%E6%B4%9B%E8%B0%B7-P3714-BJOI2017-%E6%A0%91%E7%9A%84%E9%9A%BE%E9%A2%98/#) 单调队列优化太难搞了。。线段树合并比较好。。 对于树上的各个链，状态无非三种 1. 过根节点，在两棵子树里。 2. 在一棵子树里 3. 过根节点但是在一棵子树里 对于以上三种状态的话，还是第一种实现难度比较大，但是我们可以分类讨论，并且记录上一条边的颜色与现在扫到的边进行判断，因此我们需要对于一个节点的几条边排一下序，就不能用前向星存边了，用vector数组就好了。。 线段树建立在长度上，对于种类进行维护，为了降低复杂度并且按深度运算，我们采用BFS来实现，线段树合并一下就好。 [$code$](https://www.luogu.com.cn/paste/kgn5n37a) # cdq分治 ## 前置芝士 [cdq分治1](https://ctz45562.github.io/2019/08/15/cdq%E5%88%86%E6%B2%BB%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/) [cdq分治2](https://www.cnblogs.com/flashhu/p/9381075.html) ## 例题略解 #### [P3810 【模板】三维偏序（陌上花开）](https://www.luogu.com.cn/problem/P3810) 板子题，但是由于我看了上面的blog，一下午都整到这一个题上了，所以对于上面的blog，看看思路就好... 先对于a排序，然后运用归并排序的思想，对于整个区间进行多次二分，计算贡献，然后就是**代码实现**了，我也啥也不想说了，吐了。。 [$code$](https://www.luogu.com.cn/paste/a8dhp74u) #### [P4390 [BOI2007]Mokia 摩基亚](https://www.luogu.com.cn/problem/P4390) 当然正解是cdq分治 ~~（当然**权值线段树+分块**也能过）~~,本来我打算二维分块的，后来一想这不是cdq专题么，水过去不合适（绝对不是我懒得打分块！绝对不是！） 运用前缀和的思想，所求正方形的就是大的正方形减去两个矩形，然后再加上小的正方形，注意一下边界问题就好了，一开始排序的时候第1.2.3.4关键字分别为：横坐标，纵坐标，时间，贡献。然后愉快地cdq分治就好了。 [$code$](https://www.luogu.com.cn/paste/j40dy8he) #### [P4169 [Violet]天使玩偶/SJY摆棋子](https://www.luogu.com.cn/problem/P4169) 我太菜了，调了一晚上最后还是TLE，吸了口氧气才过，差点就用双指针了，最后发现是一开始opt整成了0而不是1（雾。 比较妙的一个地方就是扫的时候只扫左下方的点然后将各个象限翻到第三象限同样的处理，然后就和之前的题目类似了。 [$code$ ](https://www.luogu.com.cn/paste/aben32gr) #### [P3157 [CQOI2011]动态逆序对](https://www.luogu.com.cn/problem/P3157) 还是cdq分治以时间先排个序，然后在进行维护，唯一不同的点就是为了减小时间复杂度，先整出后来删掉后序列的逆序对，然后向前累加就好了。 [$code$](https://www.luogu.com.cn/paste/mb5wk03y) #### [P4093 [HEOI2016/TJOI2016]序列](https://www.luogu.com.cn/problem/P4093) 中序遍历按照项从小到大转移，因此不用重新排序，另外我们分别用maxn和minn分别记录每一项的最大值以及最小值，然后用一个f数组记录以i结尾最长上升子序列的长度,然后哦cdq分治。 [$code$](https://www.luogu.com.cn/problem/P4093) # (动态)点分树 ## 前置芝士 [动态树分治](https://oi-wiki.org/graph/dynamic-tree-divide/) ## 例题略解 #### [P3241 [HNOI2015]开店](https://www.luogu.com.cn/problem/P3241) 啥也不想说了，这破题，看yxc的讲解视频，看的差不多半个下午才感觉凑合懂了一点;然后尝试自己实现，然后又一次打开了他的视频。然后视频+VsCode=半个下午，共计一个下午，终于干出来了。 大概思路就是对于点u到v的距离，可以看作一个重心的两个子树里的两个点之间的距离，然后无限递归，直到u是某个树的重心为止，然后对于u到n个不同的v的距离，可以发现u到重心的路是必须经过的 因此我们可以暴力加和其他部分，然后对于重复的部分直接数量乘上长度就好了。为了查询更方便，我们对于每一个节点开两个vector数组分别用来维护自己和儿子，然后push_back进去一个-1和A+1当作两个边界，然后码就好了。就是这么简（du）单（liu）。 还有就是auto这种东西最好少用。。。 [$code$](https://www.luogu.com.cn/paste/lsn7lz3b) #### [P3345 [ZJOI2015]幻想乡战略游戏](https://www.luogu.com.cn/problem/P3345) [一篇码风比较好的blog](https://www.cnblogs.com/PaperCloud/p/10213065.html) 和上面那个题有一些相似，就是找带权重心嘛，也是开了两个vector分别记录某个节点的祖先以及子节点，然后就是一堆板子类的东西，求出size，重心那一类的东西。 最后在各个节点尝试枚举儿子，儿子的节点状态从父亲直接转移，需要多看一下初始化的主函数，细节比较多。。。 * 注意：不要全开long long 不然虽然在Luogu可以AC，但是在本地以及别的OJ（比如我们的校内OJ）就玄乎了。 [$code$](https://www.luogu.com.cn/paste/881qmug6)