Ne, jotka ovat ratkaisseet tehtävän Conference*, saattavat luonnostaan keksiä tämän tehtävän.
Sinulle annetaan merkkijono $S$, jonka pituus on $N$. Jokainen merkkijonon $S$ merkki on jokin merkeistä A, B, C tai ?. Erityisesti merkkijonon $S$ ensimmäinen ja viimeinen merkki ovat A.
Pituutta $N$ olevalle merkkijonolle, joka koostuu vain merkeistä A, B ja C, määritellään sen pistemäärä sellaisten kokonaislukujen $i$ ($1 \le i \le N - 1$) lukumääräksi, joilla $i$:s merkki ja $(i + 1)$:s merkki ovat eri merkit.
Sinulle annetaan $Q$ kyselyä. $i$:s kysely on seuraavanlainen:
Annetaan epänegatiiviset kokonaisluvut $X_i, Y_i, Z_i$, missä $X_i + Y_i + Z_i$ on yhtä suuri kuin ?-merkkien lukumäärä merkkijonossa $S$. Kaikkien niiden merkkijonojen joukosta, jotka saadaan korvaamalla merkkijonon $S$ ?-merkeistä $X_i$ kappaletta merkillä A, $Y_i$ kappaletta merkillä B ja $Z_i$ kappaletta merkillä C, tulosta suurin mahdollinen pistemäärä.
Syöte
Syöte annetaan seuraavassa muodossa:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Tuloste
Tulosta $Q$ riviä. Tulosta $i$:nnelle riville vastaus $i$:nteen kyselyyn.
Rajoitukset
- $N, Q, X_i, Y_i, Z_i$ ovat kokonaislukuja.
- $2 \le N \le 3 \times 10^5$
- $S$ on pituutta $N$ oleva merkkijono, joka koostuu merkeistä
A,B,Cja?. - Merkkijonon $S$ ensimmäinen ja viimeinen merkki ovat
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$ on yhtä suuri kuin
?-merkkien lukumäärä merkkijonossa $S$.
Esimerkit
Syöte 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Tuloste 1
8 6 4
Syöte 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Tuloste 2
4 8 4 10
Syöte 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
Tuloste 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
Huomautus
Ensimmäisessä esimerkissä:
- Ensimmäisessä kyselyssä merkkien korvaaminen muotoon
ABCBABCBAtuottaa pistemäärän $8$, mikä on suurin mahdollinen. - Toisessa kyselyssä merkkien korvaaminen muotoon
ABABAACAAtuottaa pistemäärän $6$. - Kolmannessa kyselyssä merkkien korvaaminen muotoon
ACCBCCCCAtuottaa pistemäärän $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf