ผู้ที่เคยแก้โจทย์ Conference* มาแล้วอาจนึกถึงปัญหานี้ขึ้นมาได้อย่างเป็นธรรมชาติ
คุณได้รับสตริง $S$ ที่มีความยาว $N$ อักขระแต่ละตัวของ $S$ คือหนึ่งใน A, B, C หรือ ? โดยเฉพาะอย่างยิ่ง อักขระตัวแรกและตัวสุดท้ายของ $S$ คือ A
สำหรับสตริงที่มีความยาว $N$ ซึ่งประกอบด้วย A, B และ C เท่านั้น ให้กำหนด คะแนน ของสตริงนั้นเป็นจำนวนของจำนวนเต็ม $i$ ($1 \le i \le N - 1$) ที่ทำให้อักขระตัวที่ $i$ และอักขระตัวที่ $(i + 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