시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 32 | 8 | 3 | 75.000% |
You are given a set $D$ of $n$ strings and a string $s$. You need to find the number of strings in the set $D$ that are lexicographically less than $s$.
The given string $s$ is modified $q$ times. Each modification is defined by a pair of an integer $k_i$ and a character $c_i$. Modification $(k_i, c_i)$ means that all characters of the string $s$, starting from $k_i$ and up to the end of the string, are replaced by the character $c_i$.
For example, let the initial string $s$ be "anatoly
", then the queries $(5, \mathtt{o})$, $(3, \mathtt{b})$, $(7, \mathtt{x})$ change the string as follows:
"anatoly
" $\to$ "anatooo
" $\to$ "anbbbbb
" $\to$ "anbbbbx
"
After each modification of the string $s$, you need to output the number of strings of the set $D$ that are lexicographically less than $s$.
String $a$ is lexicographically less than string $b$ if $a \ne b$ and one of two conditions is satisfied:
The first line contains two integers $n$ and $q$ --- the number of strings of the set $D$ and the number of modifications ($1 \le n, q \le 10^6$).
The second line contains a string $s$ consisting of no more than $10^6$ lowercase Latin letters.
The following $n$ lines contain the strings of the set $D$. Each string consists of lowercase Latin letters. The total length of the strings in $D$ does not exceed $10^6$.
The following $q$ lines contain descriptions of modifications. The description consists of the integer $k_i$ and the lowercase letter of the English alphabet $c_i$, separated by a space ($1 \le k_i \le |s|$).
The first line of output must contain the number of strings of the set $D$ that are lexicographically less than the initial string $s$.
Then output $q$ lines. In the $i$-th line, print the answer after the $i$-th modification.
4 3 anatoly boris anatooo anbbbbu anba 5 o 3 b 7 x
0 0 2 3
5 5 abcde buz ababa build a aba 1 b 3 z 2 u 4 z 1 a
3 3 3 4 4 1
In the first sample test, the string changes as follows:
"anatoly
" $\to$ "anatooo
" $\to$ "anbbbbb
" $\to$ "anbbbbx
".
anatoly
" is lexicographically less than all the strings of the set, so the answer to the problem is $0$.anatooo
" and there is an equal string in the set, but the answer to the problem is still $0$, since it is not less than the current one.anbbbbb
", which is lexicographically greater than "anatooo
" and "anba
", but less than "anbbbbu
" and "boris
", so the answer is $2$.anbbbbx
", which is lexicographically greater than "anatooo
", "anba
" and "anbbbbu
", the answer is $3$.