問題一覧 > 通常問題

No.2361 Many String Compare Queries

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : 遭難者遭難者 / テスター : 👑 ygussanyygussany とりゐとりゐ
1 ProblemId : 9048 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-23 16:45:49

問題文

英小文字からなる長さ $N$ の文字列 $S$ が与えられます。

この文字列 $S$ の $i$ 文字目から $j$ 文字目までを $S[i:j]$ と表記します。例えば、 $S=$ abcde なら $S[2:4]=$ bcd です。

$k=1,2,\ldots,Q$ に対し以下の問題に答えてください。

  • $1\le i\le j\le N$ を満たす整数の組 $(i,j)$ で、 $S[i:j]$ が $S[L_k:R_k]$ より辞書順で小さいようなものの個数を求めてください。

辞書順とは

長さ $N$ の文字列 $S$ と長さ $M$ の文字列 $T$ に対し $S$ が辞書順で $T$ より小さいとは、以下の $2$ つの条件のいずれかを満たしていることを指します。

  • ある整数 $1\le k\le \min(N,M)$ が存在し、 $S[1:k-1]$ と $T[1:k-1]$ が等しく、 $S$ の $k$ 文字目が $T$ の $k$ 文字目よりアルファベット順で小さい。
  • $N < M$ かつ $S$ と $T[1:N]$ が等しい。

制約

  • $1\le N\le 2\times 10^5$
  • $1\le Q\le 10^5$
  • $S$ は英小文字からなる長さ $N$ の文字列である。
  • $1\le L_i\le R_i\le N$

入力

$N$ $Q$
$S$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

出力

$Q$ 行出力してください。

$i$ 行目 $(1\le i\le Q)$ には、 $k=i$ の時の答えを出力してください。

サンプル

サンプル1
入力
3 3
cat
1 3
2 3
2 2
出力
4
1
0

$k=1$ の場合は $(i,j)=(1,1)$ の c 、 $(i,j)=(1,2)$ の ca 、 $(i,j)=(2,2)$ の a 、 $(i,j)=(2,3)$ の at の $4$ つが条件を満たします。

$k=2$ の場合は $(i,j)=(2,2)$ の a のみが条件を満たします。

$k=3$ の場合は条件を満たす整数の組 $(i,j)$ は存在しません。

サンプル2
入力
9 5
yukicoder
1 6
2 3
8 9
2 7
1 9
出力
41
29
9
33
44

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。