CF1886C Decreasing String 题解-526互联

p.s. 本题提到的所有 \(s_i\) 的 \(i\) 均表示 \(s\) 字符串的下标，而不是第 \(i\) 个字符串。~~因为我懒不想改了~~
每次遇到这种题都想不到最好的解决方法，~~我是不是应该把所有比赛的 C 都做一遍啊~~
容易想到 \(O(n^2)\) 的判断方法，枚举每个位置，找到满足 \(s_i>s_{i+1}\) 最左边的位置然后删掉。如果没有删最后一个
我们考虑能不能不要每次都扫一遍，而是看一下两次扫描有什么联系。
我们发现如果每次删除后不重新标号，那每次选择的 \(i\) 是递增的，因为不递增一定不优，这个很显然。
我们在扫描到 \(s_i\) 时，所有可以删去的 \(j\)，都满足：
- \(s_j\) 未被删去
- \(s_j > s_i\)
而且我们可以发现一个性质：如果 \(s_j > s_i\) 而 \(s_j\) 不能被删除，则说明 \((j,i)\) 中间隔着一个 \(s_k > s_i\)，则 \(s_j\) 一定会在 \(s_k\) 处删除。
因此我们可以使用单调栈维护每一时刻扫描到 \(i\) 时扫过的这些数中 \(s\) 的状态，每次删去一个数后让 \(p \leftarrow p-n,n \leftarrow n-1\) 即可
最终复杂度 \(O(n)\)