問題一覧 > 通常問題

No.2554 MMA String 2 (Query Version)

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : dyktr_06 / テスター : sepa38 InTheBloom Seed57_cash ryota2357
お気に入りにしたユーザー ProblemId : 10257 / 自分の提出
問題文最終更新日: 2023-11-22 09:42:52
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
MMA Contest 017 (順位表) の他の問題:

Original Problem

Link

Problem 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もしくは右上の雲マークをクリックしてアカウントを作成してください。