题解 P5108 【仰望半月的夜空】

· · 个人记录

看题解里dalao神仙做法过的

喜闻乐见的暴力*标算系列

倒着计算答案

考虑两个位置上的子串i,j(i<j)如果当前s_i\le s_j，那么在串变短的过程中s_j会一直\le s_i（显然），即串的大小关系有单调性

拿一个单调栈，每次长度变短时把新出现的子串入栈，然后不断检查栈顶的两个子串，如果符合上一段话中的条件就弹出栈顶

栈中的子串保证从下往上编号增大，字典序非严格下降（串变短时可能会从大于变成相等，但不可能变成小于），栈顶的两个保证字典序严格下降（每次加入时都检查，非严格下降的话栈顶会被弹掉）

所以每次检查完后栈顶就是当前长度的答案