点分治学习笔记
定义 点分治，顾名思义，就是通过基于点的分治的一种算法。 通常用于处理树上问题，如树上所有路径统计。 我们设一次操作的时间复杂度为 $O(1)$ ，那么一次点分治复杂度为 $O(n \log n)$ 。 具体流程 操作->分治->操作……（不知道怎么讲） 点分治的核心主要在于高效的分治，每一次都可以将所求区间大小缩短至 $\dfrac{1}{k}$ 。 因此 $T(n)=k\times T(n/k)$ ，根据主定理，时间复杂度为 $O(n \log n)$ 。 分治的关键在于从在每一次操作的树上寻找重心，易证以重心为根的每颗子树大小不超过 $\dfrac{n}{2}$ ，从而可以有效缩小操作区间，保证正确的复杂度。(其实感性也很好理解的来着) 例题 P3806 【模板】点分治1 ..
CF1661D Progressions Covering 题解
link 简化题意 给定一个长度为 $n$ 的数组 $A$ ，和一种操作。 每次操作选定长度为 $k$ 的区间 $[L,R]$ , 将 $A_L-1$，$A_{L+1}-2$ …… $A_R-k$ 。 求使 $A$ 中所有元素小于等于0所需的最小操作个数。 Sulution 一个显然的贪心思路： 从后往前枚举，对于每个大于等于1的 $A_i$，将区间 $[i-k+1,k]$ 操作 $\left\lfloor\dfrac{A_i}{k}\right\rfloor$ 次。 证明略。 暴力实现是 $O(n^2)$ 的，我们考虑维护这个操作。 因为需要区间修改，单点查询，考虑线段树，但是每次修改的值不一定，考虑转化。 发现每次修改对于区间的差分数组改变一致，于是将原数组转化为差分数组。 那么我们..