ABC213 F - Common Prefixes (500)
SuffixArrayとLCP Arrayを知っていないと解けない
コンテスト中の考察
ある文字以降というのはSuffixArrayが良さそう
共通する文字数を求めるのが$ \mathcal{O}(N)、それを$ \mathcal{O}(N^2)やるのは間に合わない
解説の解法
LCPを使うと共通する文字数が全体で$ \mathcal{O}(N)で求まる
考察するとある2点間の値はその間の最小値になる
降順と昇順でそれぞれ順に求めていく
最小値への更新は普通にやると遅いので個数をカウントすることにする
PriorityQueueやStackでの高速化が必要
追加する予定の値より今見ている値が小さくなったら終わり
そうでなければその数の個数を現在の個数に追加して、合計から引いてキューから消す
最後に今見ている値を現在の個数で追加して合計にも足す
降順昇順で答えに足す先が左と右で異なるので注意
優先度付きキューの場合キューへの出し入れがボトルネックで$ \mathcal{O}(N \log N)