Universal Cup Judging System

Universal Cup

시간 제한: 5.5 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

Kleopatra uwielbia napisy. Gdy dostaje napis $s$ o długości $n$ (składający się ze znaków $s[1], \dots, s[n]$), natychmiast zaczyna go sortować. Podczas procesu sortowania wykonuje ciąg zamian postaci $s[i] \leftrightarrow s[i + 1]$, gdzie $i \in \{1, 2, \dots, n - 1\}$. Na koniec zwraca posortowany napis i żąda liczby złotych monet równej sumie indeksów $i$ ze wszystkich wykonanych zamian (jeśli zamiana została wykonana wielokrotnie dla tego samego $i$, to owo $i$ zostanie policzone w sumie tyle razy, ile razy wykonano zamianę). Kleopatra nie jest rozrzutna: spośród wszystkich sposobów posortowania napisu wybiera ten, przy którym liczba monet otrzymanych za sortowanie jest minimalna.

Katarzyna Medycejska również uwielbia napisy. Ma napis o długości $n$ i chce się nim pobawić. Konkretnie interesują ją następujące operacje:

  1. "1 i c" — zamień $s[i]$ na $c$;
  2. "2 i j" — weź kopię podsłowa napisu $s$ od $i$-tego do $j$-tego znaku włącznie ($i \le j$) i posortuj ją, podczas gdy znaki napisu $s$ pozostają bez zmian.
  3. "3 i j" — wytnij podsłowo napisu $s$ od $i$-tego do $j$-tego znaku włącznie ($i \le j$), posortuj je i wstaw z powrotem do napisu $s$ na to samo miejsce.

Katarzyna Medycejska potrafi sama obsłużyć zapytania pierwszego typu, ale zapytania drugiego i trzeciego typu są zbyt skomplikowane, więc uda się z nimi do Kleopatry. Przy wycenie kosztu tej procedury Kleopatra będzie sumować nie indeksy z napisu $s$ (od $i$ do $j$), lecz indeksy liczone względem początku podsłowa (od $1$ do $j - i + 1$).

Katarzyna Medycejska również nie jest rozrzutna i uważnie pilnuje swojego budżetu. Dlatego dla każdego jej zlecenia skierowanego do Kleopatry oblicz, ile złotych monet Katarzyna Medycejska będzie musiała wydać.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą $t$ — liczbę przypadków testowych ($1 \le t \le 3 \cdot 10^5$). Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $q$ — długość napisu oraz liczbę zapytań ($1 \le n, q \le 3 \cdot 10^5$). Następny wiersz zawiera napis złożony z $n$ wielkich liter alfabetu angielskiego. Kolejne $q$ wierszy opisuje zapytania. Każdy opis zapytania należy do jednego z trzech typów:

  1. "1 i c" — zamień $s[i]$ na $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$);
  2. "2 i j" — wyznacz koszt posortowania podsłowa $s[i..j]$, podczas gdy napis $s$ pozostaje bez zmian ($1 \le i, j \le n$);
  3. "3 i j" — wyznacz koszt posortowania podsłowa $s[i..j]$, przy czym podsłowo $s[i..j]$ w napisie $s$ zostaje zastąpione posortowanym ($1 \le i, j \le n$).

W każdym przypadku testowym wystąpi co najmniej jedno zapytanie drugiego lub trzeciego typu.

Suma $n$ po wszystkich przypadkach testowych wynosi co najwyżej $3 \cdot 10^5$. Suma $q$ po wszystkich przypadkach testowych wynosi co najwyżej $3 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w osobnych wierszach odpowiedzi na wszystkie zapytania drugiego i trzeciego typu, czyli liczbę monet, które Kleopatra otrzyma za każde z sortowań.

Przykłady

Wejście 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

Wyjście 1

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

Wejście 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

Wyjście 2

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

Uwaga

Rozważmy pierwszy przykład. Początkowy napis w nim to "DBCAA". Przejdźmy po kolei przez wszystkie 20 zapytań:

  1. Zapytanie "2 1 5". Bieżący napis: "DBCAA". Podsłowo $t[1..5]$ = "DBCAA", odpowiedź: 18. Napis się nie zmienia.
  2. Zapytanie "2 2 4". Napis: "DBCAA". Podsłowo $t[2..4]$ = "BCA", odpowiedź: 3. Napis się nie zmienia.
  3. Zapytanie "1 3 Z". Aktualizacja: $t[3] \leftarrow$ "Z". Było "DBCAA", teraz "DBZAA".
  4. Zapytanie "2 1 3". Napis: "DBZAA". Podsłowo $t[1..3]$ = "DBZ", odpowiedź: 1. Napis się nie zmienia.
  5. Zapytanie "3 1 5". Napis: "DBZAA". Podsłowo $t[1..5]$ = "DBZAA", odpowiedź: 16. Po zmianie, sortowanie podsłowa: "DBZAA" $\rightarrow$ "AABDZ". Napis stał się równy "AABDZ".
  6. Zapytanie "2 1 5". Napis: "AABDZ". Podsłowo "AABDZ", odpowiedź: 0. Napis się nie zmienia.
  7. Zapytanie "1 5 A". Było "AABDZ", teraz "AABDA".
  8. Zapytanie "3 2 4". Napis: "AABDA". Podsłowo $t[2..4]$ = "ABD", odpowiedź: 0. Po posortowaniu "ABD" się nie zmienia, napis pozostaje równy "AABDA".
  9. Zapytanie "2 1 5". Napis: "AABDA". Podsłowo "AABDA", odpowiedź: 7. Napis się nie zmienia.
  10. Zapytanie "1 1 C". Było "AABDA", teraz "CABDA".
  11. Zapytanie "2 1 2". Napis: "CABDA". Podsłowo $t[1..2]$ = "CA", odpowiedź: 1. Napis się nie zmienia.
  12. Zapytanie "3 4 5". Napis: "CABDA". Podsłowo $t[4..5]$ = "DA", odpowiedź: 1. Po zmianie: "DA" $\rightarrow$ "AD". Napis stał się równy "CABAD".
  13. Zapytanie "2 3 5". Napis: "CABAD". Podsłowo $t[3..5]$ = "BAD", odpowiedź: 1. Napis się nie zmienia.
  14. Zapytanie "1 2 B". Było "CABAD", teraz "CBBAD".
  15. Zapytanie "2 1 5". Napis: "CBBAD". Podsłowo "CBBAD", odpowiedź: 9. Napis się nie zmienia.
  16. Zapytanie "3 1 1". Napis: "CBBAD". Podsłowo $t[1..1]$ = "C", odpowiedź: 0. Sortowanie długości 1 nic nie zmienia, napis pozostaje równy "CBBAD".
  17. Zapytanie "2 1 1". Napis: "CBBAD". Podsłowo $t[1..1]$ = "C", odpowiedź: 0. Napis się nie zmienia.
  18. Zapytanie "1 4 D". Było "CBBAD", teraz "CBBDD".
  19. Zapytanie "2 1 5". Napis: "CBBDD". Podsłowo $t[1..5]$ = "CBBDD", odpowiedź: 3. Napis się nie zmienia.
  20. Zapytanie "3 1 5". Napis: "CBBDD". Podsłowo $t[1..5]$ = "CBBDD", odpowiedź: 3. Po zmianie: "CBBDD" $\rightarrow$ "BBCDD". Ostateczny napis to "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.