求出后缀数组 $rk$，分析答案数组的性质，如果 $s[l,r]$ 满足对于整个串的 SA 数组有 $rk_l=\min_{i=l}^rrk_i$，那么这个子串成为并非 lyndon 串只能依靠非平凡且非空的 border。那么对于答案数组 $p_0=0,p_1,p_2,\cdots,p_k,p_{k+1}=n$ 一定有 $rk_{p_k+1}$ 并非 $rk$ 的后缀 $\min$，而 $rk_{p_i+1}(i\leq k-1)$ 都是后缀 $\min$ 并且这一段有非平凡 border。

dp 然后对这个 border 的分段位置进行转移，形如贡献到 $j+1\sim\text{lcp}(i,j)$ 的位置，找到前后缀最近的位置即可求出有效的 $\mathcal O(1)$ 个转移点，使用 set 维护，结合求 SA 的过程，时间复杂度是大常数 $\mathcal O(n\log n)$。

不太有营养，但是好像能过阿？

fast_photon 教的/bx

考虑从递归子问题的角度来做，不妨设最小的字符是 a，发现若 $s_1>a$ 那么就直接赢了，否则 $s_1=a$。

若有且仅有一个 a 那么直接输掉了，否则考虑讨论剩余 a 的分布：

• 若 $s$ 中所有 a 都堆在开头，若只有 $1$ 个那么直接输掉；否则，考察第一个串，那么前面的分布无论如何都是没有影响的，因此可以另第一个串就是这些 a；递归到后面的后缀接着做。
• 若 $s$ 中至少有三个 a：找到第一个 a 连续段的末尾且不是 $1$ 并且后面还存在 a，将其断开作为第一个串，后面至少有一个 a 所以可以成为答案；如果没有这种结构那么整个串一定合法。
• 接下来 $s$ 只有两个 a，提取另一个 a 的出现位置 $p>2$，则第一个分割点一定在 $p$ 的后面。取出 $1,p$ 的 LCP 为 $k$，如果 LCP 内的部分是存在逆序对的，那么按照 $p$ 进行分割就直接赢了。考虑 LCP 后的两个字符是 $x,y$，若 $x\leq y$ 那么整个串一定不是 lyndon 串，就赢了。否则此时 LCP 是单调不降的。
  • 考虑 LCP 的最后一个极长连续段是字符 $c$。如果 $c$ 严格大于后缀 $\min$，直接按照 $p$ 分段就结束了；否则考虑把这些 $c$ 从最后切掉（划分到后面），然后递归到后缀的子问题继续判定。
  • 正确性：当 $c$ 小于后面的 $\min$ 时，什么都干不了，相当于一个分界点，就需要先把 $c$ 弹出。若 $c$ 等于后缀 $\min$ 时，如果后缀不以 $c$ 开头就直接赢了；否则前面加上一段 $c$ 是不劣的。

容易发现，暴力求 LCP 并同时进行以上判定，时间复杂度 $\mathcal O(n)$。