题解：CF2157F Git Gud

· · 题解

这种 \sqrt{}8 题目写了 1h 多，无敌了。

每个点都要被操作一次，而我们希望通过合并减少 \sum{l}，但是上升序列会带来 1000 的惩罚。

考虑分块，分块总是能减次数的，设块长为 B，令每个块都合并到右端点上，我们按照块倒着扫，块内正着扫，则惩罚次数为 B-1。

设总数为 m，最后合并的时候直接暴力合并，惩罚为 \frac{m}{b}。

直接分一次过不了，分两次，块长为 \sqrt[3]{n}=63 即可，上界很松，代码实现的话，取一些因数会更好写，不用取 63 也可以过。

次数约为 3n+1000\frac{n}{Bb}。

AClink.