Universal Cup Judging System

Universal Cup

実行時間制限: 5.5 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

קليאופטרה אוהבת מחרוזות. כאשר ניתנת לה מחרוזת $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.