Universal Cup Judging System

Universal Cup

時間限制: 5.5 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Клеопатра любить рядки. Коли їй дають рядок $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.