P4891 做题笔记

E1_de5truct0r · 2023-01-01 11:24:39 · 个人记录

应该是个线段树 / 分块。看到了那个每次修改递增，但是还没找到啥好性质。

感觉这坨东西没法线段树啊，直接分块。每个块先维护那个要求的值，然后每次查询全部乘起来。

考虑修改，如果改的 b 数组，那就直接改然后重构；改的 c 相当于对后面的全部进行取 \max 操作。

然后考虑这个取 \max 怎么办。可以打懒标记，然后就发现不会做了，所以看题解或者换一道题。

感觉应该可以分类讨论：

令 now 表示取 \max 后的值。

所以其实就是对所有 c<b 的，把 c 改成 \min(b,now)。

然后发现还是没什么用捏。不过两个数取 \min 可以分开讨论，即 \min 为第一个数，和 \min 为第二个数的情况。

所以只需要把 c<now<b 的个数 cnt 统计了，其他的乘积 P 求出来，答案就是 P \cdot now^{cnt}。

统计自然简单，但是 P 不太好求……？不过容易发现一定是从 4 到 3 再到 2 的这个过程，所以每个数其实变更的状态应该只会被算 3 次（？）

然后就考虑怎么维护变更状态的数。可以二分，但是这样复杂度太高了。应该可以双指针，但是没想好具体实现。

脑子一团乱麻，你妈的真烦。

突然想到了势能线段树……？好像不太可做但是复杂度摊下来好像是每次 \log^2 的，又没毛病。管他复杂度对不对先写一手。

分析了下复杂度，每次递归到叶子会让势能 -1，单点修改势能 +1，所以势能最多 n+q，然后每次都递归到叶子，发现复杂度好像也许似乎确实差不多不一定不会不可能不是不应该是对的，就做完了。