Universal Cup Judging System

Universal Cup

Süre Sınırı: 5.5 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

คลีโอพัตราหลงใหลในสตริง เมื่อเธอได้รับสตริง $s$ ความยาว $n$ (ประกอบด้วยอักขระ $s[1], \dots, s[n]$) เธอจะเริ่มเรียงลำดับมันทันที ในระหว่างกระบวนการเรียงลำดับ เธอจะทำการสลับตำแหน่งในรูปแบบ $s[i] \leftrightarrow s[i + 1]$ ต่อเนื่องกัน โดยที่ $i \in \{1, 2, \dots, n - 1\}$ ในตอนท้าย เธอจะส่งคืนสตริงที่เรียงลำดับแล้วและเรียกร้องเหรียญทองเป็นจำนวนเท่ากับผลรวมของค่า $i$ สำหรับการสลับทั้งหมดที่ทำไป (หากมีการสลับหลายครั้งด้วยค่า $i$ เดียวกัน ค่า $i$ นั้นจะถูกนับรวมในผลรวมตามจำนวนครั้งที่มีการสลับ) คลีโอพัตราไม่ใช่คนฟุ่มเฟือย ในบรรดาวิธีการเรียงลำดับสตริงทั้งหมด เธอจะเลือกวิธีที่ทำให้จำนวนเหรียญที่เธอได้รับจากการเรียงลำดับมีค่าน้อยที่สุด

แคทเธอรีน เดอ เมดีชี ก็หลงใหลในสตริงเช่นกัน เธอมีสตริงความยาว $n$ และต้องการเล่นกับมัน กล่าวโดยเฉพาะเจาะจงคือ เธอสนใจการดำเนินการต่อไปนี้:

  1. "1 i c" — แทนที่ $s[i]$ ด้วย $c$;
  2. "2 i j" — สำเนาสตริงย่อยของ $s$ ตั้งแต่อักขระตัวที่ $i$ ถึงตัวที่ $j$ รวมขอบ ($i \le j$) แล้วนำมาเรียงลำดับ ในขณะที่อักขระของสตริง $s$ ยังคงไม่เปลี่ยนแปลง
  3. "3 i j" — ดึงสตริงย่อยของ $s$ ตั้งแต่อักขระตัวที่ $i$ ถึงตัวที่ $j$ รวมขอบ ($i \le j$) ออกมาเรียงลำดับ แล้วใส่กลับเข้าไปในสตริง $s$ ที่ตำแหน่งเดิม

แคทเธอรีน เดอ เมดีชี สามารถจัดการคำถามประเภทแรกได้ด้วยตัวเอง แต่คำถามประเภทที่สองและสามซับซ้อนเกินไป เธอจึงต้องไปพึ่งคลีโอพัตรา ในการประเมินค่าใช้จ่ายของขั้นตอนนี้ คลีโอพัตราจะไม่รวมดัชนีจากสตริง $s$ (ตั้งแต่ $i$ ถึง $j$) แต่จะรวมดัชนีสัมพัทธ์เทียบกับจุดเริ่มต้นของสตริงย่อย (ตั้งแต่ $1$ ถึง $j - i + 1$)

แคทเธอรีน เดอ เมดีชี ก็ไม่ใช่คนฟุ่มเฟือยและคอยตรวจสอบงบประมาณของเธออย่างรอบคอบ ดังนั้น สำหรับแต่ละคำขอที่เธอส่งให้คลีโอพัตรา จงคำนวณว่าแคทเธอรีน เดอ เมดีชี จะต้องจ่ายเหรียญทองกี่เหรียญ

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $t$ — จำนวนชุดข้อมูลทดสอบ ($1 \le t \le 3 \cdot 10^5$) สำหรับแต่ละชุดข้อมูลทดสอบ:

บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวนคือ $n$ และ $q$ — ความยาวของสตริงและจำนวนคำถาม ($1 \le n, q \le 3 \cdot 10^5$) บรรทัดถัดไปประกอบด้วยสตริงของตัวอักษรภาษาอังกฤษพิมพ์ใหญ่จำนวน $n$ ตัว อีก $q$ บรรทัดถัดไปอธิบายคำถาม คำอธิบายของแต่ละคำถามจะเป็นหนึ่งในสามประเภทต่อไปนี้:

  1. "1 i c" — แทนที่ $s[i]$ ด้วย $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$);
  2. "2 i j" — หาค่าใช้จ่ายในการเรียงลำดับสตริงย่อย $s[i..j]$ โดยที่สตริง $s$ ไม่เปลี่ยนแปลง ($1 \le i, j \le n$);
  3. "3 i j" — หาค่าใช้จ่ายในการเรียงลำดับสตริงย่อย $s[i..j]$ โดยที่สตริงย่อย $s[i..j]$ ในสตริง $s$ จะถูกแทนที่ด้วยสตริงย่อยที่เรียงลำดับแล้ว ($1 \le i, j \le n$)

ในแต่ละชุดข้อมูลทดสอบ จะมีคำถามประเภทที่สองหรือสามอย่างน้อยหนึ่งคำถาม

ผลรวมของ $n$ จากทุกชุดข้อมูลทดสอบไม่เกิน $3 \cdot 10^5$ ผลรวมของ $q$ จากทุกชุดข้อมูลทดสอบไม่เกิน $3 \cdot 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงคำตอบของคำถามประเภทที่สองและสามทั้งหมดแยกบรรทัดกัน กล่าวคือ จำนวนเหรียญที่คลีโอพัตราจะได้รับสำหรับการเรียงลำดับแต่ละครั้ง

ตัวอย่าง

ข้อมูลนำเข้า 1

1
5 20
DBCAA
2 1 5
2 2 4
1 3 Z
2 1 3
3 1 5
2 1 5
1 5 A
3 2 4
2 1 5
1 1 C
2 1 2
3 4 5
2 3 5
1 2 B
2 1 5
3 1 1
2 1 1
1 4 D
2 1 5
3 1 5

ข้อมูลส่งออก 1

18
3
1
16
0
0
7
1
1
1
9
0
0
3
3

ข้อมูลนำเข้า 2

3
3 5
CBA
2 1 3
3 1 3
2 1 3
1 2 C
2 1 2
5 5
ABCDE
2 2 5
1 5 A
2 1 5
3 1 5
2 1 5
6 5
YYYYYY
2 1 6
1 3 A
2 1 6
3 2 5
2 1 6

ข้อมูลส่งออก 2

4
4
0
0
0
9
9
0
0
3
1
1

หมายเหตุ

พิจารณาตัวอย่างแรก ในตัวอย่างนี้ สตริงเริ่มต้นคือ "DBCAA" เรามาดูคำถามทั้ง 20 ข้อตามลำดับกัน:

  1. คำถาม "2 1 5". สตริงปัจจุบัน: "DBCAA". สตริงย่อย $t[1..5]$ = "DBCAA", คำตอบ: 18. สตริงไม่เปลี่ยนแปลง
  2. คำถาม "2 2 4". สตริง: "DBCAA". สตริงย่อย $t[2..4]$ = "BCA", คำตอบ: 3. สตริงไม่เปลี่ยนแปลง
  3. คำถาม "1 3 Z". อัปเดต: $t[3] \leftarrow$ "Z". เดิมคือ "DBCAA" ตอนนี้เป็น "DBZAA"
  4. คำถาม "2 1 3". สตริง: "DBZAA". สตริงย่อย $t[1..3]$ = "DBZ", คำตอบ: 1. สตริงไม่เปลี่ยนแปลง
  5. คำถาม "3 1 5". สตริง: "DBZAA". สตริงย่อย $t[1..5]$ = "DBZAA", คำตอบ: 16. หลังการแก้ไข เรียงลำดับสตริงย่อย: "DBZAA" $\rightarrow$ "AABDZ" สตริงกลายเป็น "AABDZ"
  6. คำถาม "2 1 5". สตริง: "AABDZ". สตริงย่อย "AABDZ", คำตอบ: 0. สตริงไม่เปลี่ยนแปลง
  7. คำถาม "1 5 A". เดิมคือ "AABDZ" ตอนนี้เป็น "AABDA"
  8. คำถาม "3 2 4". สตริง: "AABDA". สตริงย่อย $t[2..4]$ = "ABD", คำตอบ: 0. หลังการเรียงลำดับ "ABD" ไม่เปลี่ยนแปลง สตริงยังคงเป็น "AABDA"
  9. คำถาม "2 1 5". สตริง: "AABDA". สตริงย่อย "AABDA", คำตอบ: 7. สตริงไม่เปลี่ยนแปลง
  10. คำถาม "1 1 C". เดิมคือ "AABDA" ตอนนี้เป็น "CABDA"
  11. คำถาม "2 1 2". สตริง: "CABDA". สตริงย่อย $t[1..2]$ = "CA", คำตอบ: 1. สตริงไม่เปลี่ยนแปลง
  12. คำถาม "3 4 5". สตริง: "CABDA". สตริงย่อย $t[4..5]$ = "DA", คำตอบ: 1. หลังการแก้ไข: "DA" $\rightarrow$ "AD" สตริงกลายเป็น "CABAD"
  13. คำถาม "2 3 5". สตริง: "CABAD". สตริงย่อย $t[3..5]$ = "BAD", คำตอบ: 1. สตริงไม่เปลี่ยนแปลง
  14. คำถาม "1 2 B". เดิมคือ "CABAD" ตอนนี้เป็น "CBBAD"
  15. คำถาม "2 1 5". สตริง: "CBBAD". สตริงย่อย "CBBAD", คำตอบ: 9. สตริงไม่เปลี่ยนแปลง
  16. คำถาม "3 1 1". สตริง: "CBBAD". สตริงย่อย $t[1..1]$ = "C", คำตอบ: 0. การเรียงลำดับความยาว 1 ไม่เปลี่ยนแปลงอะไร สตริงยังคงเป็น "CBBAD"
  17. คำถาม "2 1 1". สตริง: "CBBAD". สตริงย่อย $t[1..1]$ = "C", คำตอบ: 0. สตริงไม่เปลี่ยนแปลง
  18. คำถาม "1 4 D". เดิมคือ "CBBAD" ตอนนี้เป็น "CBBDD"
  19. คำถาม "2 1 5". สตริง: "CBBDD". สตริงย่อย $t[1..5]$ = "CBBDD", คำตอบ: 3. สตริงไม่เปลี่ยนแปลง
  20. คำถาม "3 1 5". สตริง: "CBBDD". สตริงย่อย $t[1..5]$ = "CBBDD", คำตอบ: 3. หลังการแก้ไข: "CBBDD" $\rightarrow$ "BBCDD" สตริงสุดท้ายคือ "BBCDD"

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1214EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.