2021.11.03模拟赛

Turn into a shooting star that briefly shines but warms up every heart

求出来每个 $\mathrm{cnt}(i)$ 左下前缀和即可，求的过程可以 $O(n \log v)$ 分解质因子做

二分答案，设 $dp_{i}$ 为 $i$ 号点不修改的最小修改次数，枚举 $j \in [1,i-1]$ 若 $|h_i-h_j| \le (i-j)mid$ 则可以修改 $i-j-1$ 个点达成条件

最后取 $\min(dp_i+n-i) \le k$

CF280D 的环上版本

考虑序列上费用流怎么做，就是从 $S$ 到每个点流量为 $1$ ，每个点向下一个流量为 $1$ 费用为 $a_i$ 每个点向 $T$ 连边

图很特殊，可以手玩，没一次流肯定是流最大子段和的一段，然后他们的流量取反，所以在原序列上也这么做

线段树维护可以做到 $m\log n$ ，环考虑每次是取最大子段和还是总和减去最小子段和的一段即可

对每一位维护状态，分别是相同/相反/恒0/恒1

线段树维护即可

可以不用带 $\log w$ ，只要对 $0$ 和 $2^k-1$ 维护值就可以得到每一位是 $0/1$ 的状态了