No.2454 Former < Latter
タグ : / 解いたユーザー数 84
作問者 :
srjywrdnprkt
/ テスター :
👑 Problem Statement
You are given a string $S=S_1S_2\cdots S_N$ of length $N$ consisting only of lowercase English letters.
Among the integers $i$ satisfying $1\leq i\leq N-1$, find the total number of those for which, letting $U=S_1\cdots S_i$ be the first part and $V=S_{i+1}\cdots S_N$ be the second part of the strings obtained by splitting $S$ at the $i$-th character, $U$ is strictly smaller than $V$ in lexicographical order.
You are given $T$ test cases; find the answer for each of them.
Input
$T$ $case_1$ $\vdots$ $case_T$Here, $case_i$ is the $i$-th test case. Each test case is given in the following format.
$N$ $S$
The input satisfies the following constraints.
- $T, N$ are integers
- $1\leq T$
- $2\leq N$
- $S$ is a string of length $N$ consisting only of lowercase English letters
- For the test cases contained in $1$ input, the sum of their $N$ does not exceed $3\times 10^5$.
Output
Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.
Sample
Sample 1
Input
3 6 banana 26 abcdefghijklmnopqrstuvwxyz 7 xxxxxxx
Output
2 25 3
For test case number $1$,
- When $i=1$, $U=b, V=anana$ and $U > V$.
- When $i=2$, $U=ba, V=nana$ and $U < V$.
- When $i=3$, $U=ban, V=ana$ and $U > V$.
- When $i=4$, $U=bana, V=na$ and $U < V$.
- When $i=5$, $U=banan, V=a$ and $U > V$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。