解決過 Conference* 嘅人自然會諗到呢個問題。
畀你一個長度為 $N$ 嘅字符串 $S$。$S$ 入面嘅每個字符都係 A、B、C 或者 ? 之一。特別地,$S$ 嘅第一個同最後一個字符都係 A。
對於一個僅由 A、B 同 C 組成嘅長度為 $N$ 嘅字符串,定義佢嘅得分為滿足第 $i$ 個字符同第 $(i + 1)$ 個字符唔同嘅整數 $i$($1 \le i \le N - 1$)嘅個數。
畀你 $Q$ 個查詢。第 $i$ 個查詢如下:
給定非負整數 $X_i, Y_i, Z_i$,其中 $X_i + Y_i + Z_i$ 等於 $S$ 入面 ? 字符嘅數量。喺透過將 $S$ 入面嘅 $X_i$ 個 ? 字符替換為 A,$Y_i$ 個替換為 B,$Z_i$ 個替換為 C 得到嘅所有字符串入面,輸出可能嘅最大得分。
輸入格式
輸入按以下格式畀出:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
輸出格式
輸出 $Q$ 行。第 $i$ 行輸出第 $i$ 個查詢嘅答案。
數據範圍
- $N, Q, X_i, Y_i, Z_i$ 係整數。
- $2 \le N \le 3 \times 10^5$
- $S$ 係一個長度為 $N$ 嘅字符串,由
A、B、C同?組成。 - $S$ 嘅第一個同最後一個字符都係
A。 - $1 \le Q \le 2 \times 10^5$
- $0 \le X_i$
- $0 \le Y_i$
- $0 \le Z_i$
- $X_i + Y_i + Z_i$ 等於 $S$ 入面
?字符嘅數量。
樣例
輸入樣例 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
輸出樣例 1
8 6 4
輸入樣例 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
輸出樣例 2
4 8 4 10
輸入樣例 3
28 ACB??B???BCB??B????B?AAA?BBA 26 6 1 6 4 5 4 2 3 8 9 2 2 11 0 2 8 4 1 11 0 2 2 0 11 0 1 12 12 1 0 10 3 0 1 4 8 3 7 3 2 8 3 1 3 9 11 1 1 7 0 6 6 4 3 8 4 1 0 10 3 13 0 0 11 1 1 0 6 7 2 8 3 9 0 4 0 0 13
輸出樣例 3
24 21 23 21 19 20 19 21 19 17 19 22 19 17 22 19 23 22 20 13 15 19 20 17 21 17
說明
喺第一個樣例入面:
- 對於第一個查詢,將字符替換為
ABCBABCBA得到嘅得分為 $8$,呢個係可能嘅最大得分。 - 對於第二個查詢,將字符替換為
ABABAACAA得到嘅得分為 $6$。 - 對於第三個查詢,將字符替換為
ACCBCCCCA得到嘅得分為 $4$。
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf