F - ngng 文字列
ผักชี
3
s
1024
MB
100
点
問題文
英小文字からなる長さ $N$ の文字列 $S$ が与えられます。$S$ の $i$ 番目の文字を $S_i$ とします。
$Q$ 個のクエリが与えられるので、処理してください。
$i$ 番目のクエリでは整数 $L_i, R_i$ が与えられるので、以下の問題を解いてください。
- 次の条件をすべて満たす整数の組 $(a, b, c, d)$ の個数を求めてください。
- $L_i \le a < b < c < d \le R_i$
- $S_a = S_c$
- $S_b = S_d$
- $S_a \ne S_b$
制約
- $4 \le N \le 30{,}000$
- $1 \le Q \le 100{,}000$
- $S$ は英小文字からなる長さ $N$ の文字列
- $1 \le L_i \le R_i \le N$
- $N, Q, L_i, R_i$ は整数
部分点
この問題に部分点は存在しません。
入力
入力は以下の形式で標準入力から与えられます。
$N\ \ Q$
$S$
$L_1\ \ R_1$
$L_2\ \ R_2$
$\ \vdots$
$L_Q\ \ R_Q$
出力
標準出力に $Q$ 行出力してください。
$i$ 行目には、$i$ 番目のクエリの答えを出力してください。
入力例 1
6 2
abaaab
1 6
1 4
出力例 1
3
0
$S$ は abaaab です。
$1$ 番目のクエリにおいて、条件を満たす $(a, b, c, d)$ の組は $(1, 2, 3, 6), (1, 2, 4, 6), (1, 2, 5, 6)$ の $3$ つです。($(1, 3, 4, 5)$ が条件を満たさないことに注意してください。)
よって $1$ 行目には $3$ を出力します。
$2$ 番目のクエリにおいて、条件を満たす $(a, b, c, d)$ の組は存在しません。
よって $2$ 行目には $0$ を出力します。
入力例 2
41 5
tokyouniversityofagricultureandtechnology
6 28
2 22
20 36
1 35
1 41
出力例 2
20
13
7
123
245
$S$ は英小文字のみからなる文字列であることが保証されています。
入力例 3
10 5
gnngggngnn
1 9
1 10
2 9
2 10
3 9
出力例 3
24
36
9
12
6