势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446
势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093792
https://www.luogu.com.cn/problem/P7446
https://www.luogu.com.cn/problem/CF1491H
看到题，发现只有减，就和势能有关。维护势能，像这种题，树形ds显然不好做，所以可以去考虑进行分块。
考虑分块。每个块记录一个 ， 的最深而且不在同一个块的祖先的编号。
考虑动态维护，散块重构。对于大块，如果操作次数超过 ，显然不会变（此时它的父亲已经在上一块了。）
好了，显然要询问了。我们想一想树剖我们是怎么询问lca的。如果两点不在同一条链上，那么就由深的去挑。这题同理，我们直接用块后的去跳到 即可。
如果不在同一块，那就偏后的跳。如果同一个块，但 不相同，则一起跳。如果相同，就是编号打的跳父亲。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-16
【P2325 [SCOI2005]王室联邦】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15564095.html 题目链接 题目 “余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。 他的国家有 NNN 个城市，编号为 1…N1\ldots N1…N。 一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。 为了防止管理太过分散，每个省至少要有 BBB 个城市。 为了能有效的管理，每个省最多只有 3×B3\times B3×B 个城市。 每个省必须有一个省会...
2023-10-04
与值域有关的问题（非权值线段树）——运用分块：1004T1
与值域有关的问题（非权值线段树）——运用分块：1004T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133560662 区间小于等于某值 区间加 显然同时涉及区间和值域，不能用log级ds来做，常见套路就是上分块 这题是个复合题，后面就是个组合数 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535...
2022-07-28
【P2261 [CQOI2007]余数求和】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16529601.html 题目地址 题目 给出正整数 nnn 和 kkk，请计算 G(n,k)=∑i=1nk mod iG(n, k) = \sum_{i = 1}^n k \bmod i G(n,k)=i=1∑nkmodi 其中 k mod ik\bmod ikmodi 表示 kkk 除以 iii 的余数。 思路 数论分块 下面除法默认下取整 G(n,k)=∑i=1nk mod i=∑i=1n(k−ki×i)=n×k−∑i=1ni×ki\L...
2023-10-08
长链贪心+虚树+类直径合并性+分块建树维护ST表：1008T4
长链贪心+虚树+类直径合并性+分块建树维护ST表：1008T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133690843 http://47.92.197.167:5283/contest/408/problem/4 两个可以推的经典套路： 我们可以对所有点建序树，然后取前 kkk 大。而取前 kkk 大可以通过以直径端点为根长剖来贪心 直径具有合并性（不仅是连通块，而且是点集）。同理，前 kkk 大的点也具有合并性。 想到这里，我们就已...
2023-09-19
多观察题目性质：0919T3
多观察题目性质：0919T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133047414 http://cplusoj.com/d/senior/p/SS230919C 本题难点在于观察题目性质 对于 p=1p=1p=1 ，必然只能放在自己本身 对于 p=2p=2p=2 ，首先必然满足对称性 满足对称性后，在往中间扩散时，必然更劣 所以必然其中以一边为1 然后就可以上树状数组了 1234567891011121314151617181920212223...
2023-08-08
通过数据结构维护数论分块结果：ZR2609
通过数据结构维护数论分块结果：ZR2609 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132178041 http://zhengruioi.com/problem/2609 对于 这类东西，应该是自然反应，枚举个 aia_iai ，然后数论分块，这里是 O(nn)O(n\sqrt n)O(nn) 然后会在纸上推一大轮（结论忘了）推出 xxx 的合法区间 [l,r][l,r][l,r] ，然后就是判断 aj∈[l,r]a_j\in[l,r]aj∈...