比赛链接

Upsolved by qxforever.

对于一个字符串 $s$，定义 $b_i=\min_{1\le j<i,s_j=s_i}i-j$ ，若不存在这样的 $j$ ，则 $b_i=0$ 。

给一个长度为 $n$ 的字符串 $s$ ，求所有后缀的 $b$ 数组的字典序。$\sum n\le10^6$ ，字符集 $\{a,b\}$ 。

对于一个后缀 $t$ ，首先考虑 $t$ 中 a，b 同时出现的最短前缀，其长度记为 $f(t)$ 。其 $b$ 数组的开头为 $1,1,1,1\ldots.0$ 。于是若 $f(s)<f(t)$ ，则 $b(s)<b(t)$ 。

当 $f(s)=f(t)$ 时，需要比较两个串的第 $\mathrm{LCP}(s,t)+1$ 位。若 $s_{\mathrm{LCP}+1}=s_{\mathrm{LCP}}$ ，则 $b(s)<b(t)$ 。

于是我们可以 $O(1)$ 比较两个后缀 $b$ 数组的大小关系。复杂度为 $O(n\log n)$ 。

Solved by nikkukun.

给两个串，问分别无限拼起来两串哪个大。

暴力比较前 $2\times \max(l_a,l_b)$ 位即可。

Solved by WolframAlpha.

nb 题，跳了