Những ai đã giải bài Conference* có thể tự nhiên nghĩ ra bài toán này.
Bạn được cho một xâu $S$ có độ dài $N$. Mỗi ký tự của $S$ là một trong A, B, C, hoặc ?. Đặc biệt, ký tự đầu tiên và ký tự cuối cùng của $S$ đều là A.
Đối với một xâu có độ dài $N$ chỉ bao gồm A, B, và C, định nghĩa điểm của nó là số lượng số nguyên $i$ ($1 \le i \le N - 1$) sao cho ký tự thứ $i$ và ký tự thứ $(i + 1)$ là khác nhau.
Bạn được cho $Q$ truy vấn. Truy vấn thứ $i$ như sau:
Các số nguyên không âm $X_i, Y_i, Z_i$ được cho, trong đó $X_i + Y_i + Z_i$ bằng số lượng ký tự ? trong $S$. Trong tất cả các xâu thu được bằng cách thay thế $X_i$ ký tự ? trong $S$ bằng A, $Y_i$ ký tự trong số đó bằng B, và $Z_i$ ký tự trong số đó bằng C, hãy in ra số điểm lớn nhất có thể.
Dữ liệu vào
Dữ liệu vào được cung cấp theo định dạng sau:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Dữ liệu ra
In ra $Q$ dòng. Trên dòng thứ $i$, in ra câu trả lời cho truy vấn thứ $i$.
Ràng buộc
- $N, Q, X_i, Y_i, Z_i$ là các số nguyên.
- $2 \le N \le 3 \times 10^5$
- $S$ là một xâu có độ dài $N$ bao gồm
A,B,C, và?. - Ký tự đầu tiên và ký tự cuối cùng của $S$ là
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$ bằng số lượng ký tự
?trong $S$.
Ví dụ
Đầu vào 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Đầu ra 1
8 6 4
Đầu vào 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Đầu ra 2
4 8 4 10
Đầu vào 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
Đầu ra 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
Ghi chú
Trong ví dụ đầu tiên:
- Đối với truy vấn đầu tiên, thay thế các ký tự thành
ABCBABCBAmang lại số điểm là $8$, đây là mức tối đa có thể. - Đối với truy vấn thứ hai, thay thế các ký tự thành
ABABAACAAmang lại số điểm là $6$. - Đối với truy vấn thứ ba, thay thế các ký tự thành
ACCBCCCCAmang lại số điểm là $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf