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.