問題一覧 > 通常問題

No.2361 Many String Compare Queries

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 25
作問者 : 👑 qand / テスター : ygussany とりゐ
お気に入りにしたユーザー ProblemId : 9048 / 自分の提出
問題文最終更新日: 2023-06-23 16:45:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 394 (順位表) の他の問題:

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters.

The substring of $S$ from the $i$-th character through the $j$-th character is denoted by $S[i:j]$. For example, if $S=$ abcde, then $S[2:4]=$ bcd.

For each $k=1,2,\ldots,Q$, solve the following problem.

  • Find the number of pairs of integers $(i,j)$ satisfying $1\le i\le j\le N$ such that $S[i:j]$ is lexicographically smaller than $S[L_k:R_k]$.

What is lexicographical order?

For a string $S$ of length $N$ and a string $T$ of length $M$, $S$ is lexicographically smaller than $T$ if one of the following $2$ conditions holds.

  • There exists an integer $1\le k\le \min(N,M)$ such that $S[1:k-1]$ and $T[1:k-1]$ are equal, and the $k$-th character of $S$ comes before the $k$-th character of $T$ in alphabetical order.
  • $N < M$ and $S$ is equal to $T[1:N]$.

Constraints

  • $1\le N\le 2\times 10^5$
  • $1\le Q\le 10^5$
  • $S$ is a string of length $N$ consisting of lowercase English letters.
  • $1\le L_i\le R_i\le N$

Input

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

Output

Print $Q$ lines.

On the $i$-th line $(1\le i\le Q)$, print the answer for $k=i$.

Sample

Sample 1
Input
3 3
cat
1 3
2 3
2 2
Output
4
1
0

For $k=1$, the following $4$ satisfy the condition: c with $(i,j)=(1,1)$, ca with $(i,j)=(1,2)$, a with $(i,j)=(2,2)$, and at with $(i,j)=(2,3)$.

For $k=2$, only a with $(i,j)=(2,2)$ satisfies the condition.

For $k=3$, there is no pair of integers $(i,j)$ satisfying the condition.

Sample 2
Input
9 5
yukicoder
1 6
2 3
8 9
2 7
1 9
Output
41
29
9
33
44

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