====== 2020牛客暑期多校训练营（第一场） ======

[[https://ac.nowcoder.com/acm/contest/5666|比赛链接]]

===== A - B-Suffix Array =====

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....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)$ 。

===== F - Infinite String Comparision =====

Solved by nikkukun.

==== 题目描述 ====

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

==== 解题思路 ====

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

===== J - Easy Integration =====

Solved by WolframAlpha.

nb 题，跳了