問題一覧 > 通常問題

No.2992 Range ABCD String Query

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 33
作問者 : Iroha_3856 / テスター : lif4635 hiro1729
お気に入りにしたユーザー ProblemId : 11705 / 自分の提出
問題文最終更新日: 2024-12-17 00:15:11
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
Advent Calendar Contest 2024 (順位表) の他の問題:

Note

The intended solution takes about $\mathrm{650ms}$ in C++ and about $\mathrm{4500ms}$ in PyPy3.

Using a fast language is strongly recommended. With a slow language, fast I/O and non-essential, non-trivial constant-factor optimizations are likely to be required.

Problem Statement

A string $X$ is defined to be a good string if it satisfies the following condition.

  • There exist non-negative integers $x, y, z, w$ such that $X$ can be represented as the concatenation of $x$ copies of A, $y$ copies of B, $z$ copies of C, and $w$ copies of D, in this order.

For example, ABCD, AABCCD, ABC, DD, and the empty string are good strings. (Note that $x, y, z, w$ may be $0$.)

You are given a string $S$ of length $N$, each of whose characters is one of A, B, C, D.

A positive integer $Q$ is given. Process $Q$ queries in the order they are given.

Each query is of one of the following two types.

  • 1 x c:
    • A positive integer $x (1 \leq x \leq N)$ and a character $c$ that is one of A, B, C, D are given.
    • Update the $x$-th character of $S$ to the character $c$.
  • 2 L R:
    • $L, R$ satisfying $1 \leq L \leq R \leq N$ are given. Let $T$ be the (contiguous) substring of $S$ consisting of the $L$-th through $R$-th characters.
    • Perform the change operation on $T$ any number of times (possibly $0$ times) to make it a good string, and output the minimum number of change operations required.
    • Here, performing the change operation on $T$ is defined as choosing one $i$ satisfying $1 \leq i \leq |T|$ and changing the $i$-th character of $T$ to any character of your choice.

Input

$N \ Q$
$S$ 
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

Each $\mathrm{query}_i$ is given in one of the following formats. 

$1\ x\ c$
$2\ L\ R$

All inputs satisfy the following constraints.

  • $1 \leq N, Q \leq 2 \times 10 ^ 5$
  • $S$ is a string of length $N$
  • Every character of $S$ is one of A, B, C, D
  • $1 \leq x \leq N$
  • $c$ is one of A, B, C, D
  • $1 \leq L \leq R \leq N$
  • $N, Q, x, L, R$ are all integers

Output

Output the answers to the queries of the second type, separated by newlines.

Sample

Sample 1
Input
5 5
ABACD
2 2 5
1 1 D
2 1 5
1 3 D
2 1 5
Output
1
2
2

  • For the $1$-st query, $T = $ BACD. Performing $1$ operation that changes the $2$-nd character of $T$ to B turns $T$ into BBCD, which is a good string.
    It cannot be made a good string with $0$ or fewer operations, so the answer is $1$.
  • For the $2$-nd query, the $1$-st character of $S$ is changed to D, resulting in $S = $DBACD.
  • For the $3$-rd query, $T = $ DBACD. Performing $2$ operations that change the $1$-st character of $T$ to A and the $3$-rd character to B turns $T$ into ABBCD, which is a good string.
    It cannot be made a good string with $1$ or fewer operations, so the answer is $2$.
  • For the $4$-th query, the $3$-rd character of $S$ is changed to D, resulting in $S = $DBDCD.
  • For the $5$-th query, $T = $ DBDCD. Performing $2$ operations that change the $1$-st character of $T$ to A and the $3$-rd character to C turns $T$ into ABCCD, which is a good string.
    It cannot be made a good string with $1$ or fewer operations, so the answer is $2$.

Sample 2
Input
15 15
BDBADBADBBBCBDA
2 1 7
1 5 B
1 9 D
1 5 C
2 1 13
1 3 C
2 7 8
2 1 4
1 8 A
2 3 12
2 3 7
1 8 A
1 7 D
2 7 10
2 1 13
Output
4
7
0
2
4
3
2
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。