No.2361 Many String Compare Queries
問題文最終更新日: 2023-06-23 16:45:49
English (AI translation)
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)$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
とりゐ