Codeforces Round 987 赛后复盘

C. Penchick and BBQ Buns

没什么好说的，一坨屎

（分类讨论构造合法序列的知识以一种卑鄙的方式进入脑子了）

没做出来，很不应该

赛时的时候想到了 DP，也写出来了，但是在转移的时候没有考虑好，并且触发了 set 的奇妙雷区，导致代码一直过不去，都怀疑自己做法是不是有问题了，最后也是掉大分了

考虑 DP，怎么想到的呢？

最后一个位置的答案显然：前缀最大值
往回倒推，某一位置的答案就是从这个位置能跳到的最远的位置的答案，为什么？
- 向前跳只会变小，所以如果要优化答案，一定是向前跳了之后向后跳
- 如果优化后的答案不比原来大就没有任何意义，所以，往后跳到的最终位置一定会比原来高，也会比任何一个能从初始位置能跳到的最远的位置高
- 所以，为了不落下任何一个可能跳到的高位，我们选择一个一次能被跳到的最远的低位的答案
怎么求取从这个位置能跳到的最远的位置呢？
- 还是维护一个前缀最大值，往后跳到最高点，那么他能到达的最远位置就是我们要求的
那现在就好办了，从后往前倒推，复杂度 $O (n)$

注意到，这个操作是完全可逆的，所以一系列能相互跳达的位置是 “连通” 的，所以考虑使用并查集

但是需要在合并的时候做一个优化：消除子集中其他位置信息，只留下坐标最大的那一个，这样可以保证一次查询一定会消去一个节点，最后维护一个子集内最高点即可

显然地，从最高的位置开始考虑可以保证正确性，每次用当前位置的答案将其右边的位置的答案全部刷一遍取最小值，使用线段树优化，可以过