No.2554 MMA String 2 (Query Version)
タグ : / 解いたユーザー数 20
作問者 :
sepa38
Seed57_cash
Original Problem
LinkProblem Statement
An MMA string is a string of $3$ characters that consists of $2$ kinds of letters and whose $1$st and $2$nd characters are the same.
You are given a string $S$ of length $N$ consisting only of uppercase English letters.
You are given $Q$ queries; process them in order.
Each query is of one of the following $2$ types.
1 x c: Change the $x$-th character of $S$ to $c$.2 l r: Find the number of (not necessarily contiguous) subsequences of the substring $S_{l} S_{l + 1} … S_r$ of $S$ that are MMA strings.
Note that even if the extracted subsequences are equal as sequences, they are counted as different ways of extraction if the sets of chosen positions differ.
Constraints
- $3 \leq N \leq 5 \times 10^{4}$
- $S$ is a string of length $N$ consisting only of uppercase English letters
- $1 \leq Q \leq 5 \times 10^{4}$
- $1 \leq x \leq N$
- $c$ is an uppercase English letter
- $1 \leq l \leq r \leq N$
- $N, Q, x, l, r$ are integers
Input
The input is given from Standard Input in the following format.
$N$ $S$ $Q$ query $1$ query $2$ $\vdots$ query $Q$
Each query is given in one of the following $2$ formats.
$1$ $x$ $c$
$2$ $l$ $r$
Output
Let $q$ be the number of queries of type $2$. Print $q$ lines.
On the $j$-th line $(1 \leq j \leq q)$, print the answer to the $j$-th such query.
Sample
Sample 1
Input
9 CIRCLEMMA 4 2 1 9 1 8 D 2 1 9 2 2 9
Output
6 5 0
For the $1$st query, the (not necessarily contiguous) subsequences of the substring CIRCLEMMA of $S$ that are MMA strings are the following $6$.
CCL, extracting characters $1, 4, 5$CCE, extracting characters $1, 4, 6$CCM, extracting characters $1, 4, 7$CCM, extracting characters $1, 4, 8$CCA, extracting characters $1, 4, 9$MMA, extracting characters $7, 8, 9$
For the $2$nd query, $S$ becomes CIRCLEMDA.
For the $3$rd query, the (not necessarily contiguous) subsequences of the substring CIRCLEMDA of $S$ that are MMA strings are the following $5$.
CCL, extracting characters $1, 4, 5$CCE, extracting characters $1, 4, 6$CCM, extracting characters $1, 4, 7$CCD, extracting characters $1, 4, 8$CCA, extracting characters $1, 4, 9$
For the $4$th query, there are no (not necessarily contiguous) subsequences of the substring IRCLEMDA of $S$ that are MMA strings.
Sample 2
Input
24 MMACONTESTISFORBEGINNERS 8 2 1 24 2 1 12 2 10 24 1 9 N 2 1 24 1 13 P 2 2 12 2 9 16
Output
82 12 11 90 5 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。