Luogu5334 [JSOI2019]节日庆典

\(exkmp\)

容易发现，当我们处理到位置\(k\)时，对于此时的两个后缀\(i,j(i<j)\)，如果\(T_i,T_j\)均有可能在\(\ge k\)的位置成为最优解，那么一定满足\(\operatorname{lcp}(T_i,T_j) \ge k-j+1\)。

本题的突破口在于，可能成为最优解的后缀数量极少（懵）。

对于长度相邻的两个后缀\(i,j(i<j)\)，我们可以证明：\(k-j+1<j-i\)。

利用反证法，假设\(k-j+1 \le j-i\)。

设\(S_k=ABBC,T_i=BBCA,T_j=BCAB\)，\(C\)为\(B\)的前缀。

\(T_{2j-i}=CABB\)。

我们先在\(k\)的情况下观察：

\(1.\)当\(BCA \le CAB\)时，\(T_i \le T_j\)。

\(2.\)当\(BCA > CAB\)时：\(T_{2j-i}>T_j\)。

因此在\(k\)处，\(j\)不可能是最优解。

那么我们扩展到\(k'>k\)处。

\(S_{k'}=ABBCD,T'_i=BBCDA,T'_j=BCDAB,T'_{2j-i}=CDABB\)。

同理：

\(1.\)当\(BCDA \le CDAB\)时，\(T'_i \le T'_j\)。

\(2.\)当\(BCDA > CDAB\)时：\(T'_{2j-i}>T'_j\)。

因此\(j\)不可能再成为最优解了，可以直接剔除。

\(k-j+1<j-i\)，容易得到满足条件的后缀数量为\(\log k\)。

那么我们每次操作完成之后，直接暴力重构集合，利用\(exkmp\)可以\(O(1)\)比较两个后缀。

时间复杂度：\(O(n \log n)\)。