2024/02/24(#21)：天使帝国

便一去不回。

模拟赛，四天并到了一天。

最近气温是有点离谱了，达到了 $\Delta=-25^{\circ}\text{C}$ 。

直接并查集合并就没了。代码。

联考考过，没补，我是摆怪。

考虑最终序列的最大值一定不会大于原序列中的最大值，那么任取一个最大值位置作为峰顶，左右两边分开处理。

对于左边来说（右边同理），一个位置的最终值是它左边所有值的最大值。每次找到还未达到最终值的所有最小值，尝试将其全部加一。发现最优情况是从两端加到中间，于是从小到大扫，直接计算贡献即可。代码。

Techno，土豆。

暴力 DP 可以将 $i,k$ 的贡献拆开然后暴力扫然后乘起来即可。

看上去就非常的离谱，以前给出的做法大概是这样的：

直接操作分块，每次只有 $O(\sqrt{m})$ 个被修改的数，然后就有看每个数是否是在这个块内被修改的， $8$ 种情况都能做，就是有点无语。

zak 有一种聪明的做法：

算了，明天写。

今天吃晚饭的时候一人顶着伞走了一圈，有种将世间万物都收在一起的感觉。视野没有那么开阔，却也不觉遮挡。

温度在心中聚集，在一个不大的世界中，像登山者看到了在山顶开放的花一般欣喜。

走吧，不管走到哪里，这一切都很美的。

以上都是 21 日的，下面开始是 22 日和 23 日的。

先继续写那个土豆题。

转化为 $a,b,c$ 单点修改， $b_i=a_j=c_k$ 的个数。先写一个动态 DP 维护转移。

对于每个出现的 $w$ 的次数进行根号分治。对于 $cnt_w\le B$ ，那么进行暴力 DP，然后差分贡献，扔到相应的位置上，询问相当于求前缀和， $O(n\sqrt{n})$ 次修改， $O(m)$ 次查询，使用 $O(1)-O(\sqrt{n})$ 的分块维护。

对于 $cnt_w>B$ ，离线扫一遍操作序列，单点修改前缀查询，由于修改的总个数是 $O(m)$ ，询问个数是 $O(m\sqrt n)$ ，因此使用 $O(\sqrt{n})-O(1)$ 的分块维护即可。

写起来比较方便，土豆还是很美味的！！代码。

旋风牛马大数数。

考虑从后往前扫，然后假定 $1\sim h$ 的石柱各出现了一根，那么接下来出现的 $\le h$ 的柱子，都会直接震没。那些没有被震死的柱子称为“标准柱”。

继续观察性质。如果当前位置为 $x$ ，后面存在 $x\sim x-k$ ，那么 $x$ 会下降到 $x-k-1$ 。

设 $f_{i,j}$ 代表后 $i$ 个柱子，此时 $h=j$ 的方案数。

我们先假定两根高度相同的柱子实际上是不同的，那么最终答案除以 $2^n$ 即可。

倒着 DP，设此时有 $c_0$ 个钦定消失， $c_1$ 个钦定存在。

设 $g_{i,j}$ 代表用 $1\sim i$ 的数填 $j$ 个位置，放进去的最大数不影响原来能震成的值域连续段，那么能震成值域连续段的充要条件是 $i\ge j$ 。枚举第 $i$ 个数填了 $0/1/2$ 的转移方式：

$g_{i,j}=g_{i-1,j}+2j\times g_{i-1,j-1}+j(j-1) g_{i-1,j-2}$

就是求 $\sum_{i=l}^r [a_j=a_r](b_r-b_j)$ 直接莫队没有了，这东西为什么可以不丢 Easy Round？？？？代码。

教练领着去某个神秘的地方吃了一顿，挺开心的。

不过那里的猫一个都不理我

今天下午听了很多遍《斗牛》！！

野性坦露着灵魂纯粹或者肆意妄为
直到亲手栽培了原罪以后又要将它摧毁

好好休息一下呢。