Universal Cup Judging System

Universal Cup

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

Kleopatra liebt Zeichenketten. Wenn man ihr eine Zeichenkette $s$ der Länge $n$ (bestehend aus den Zeichen $s[1], \dots, s[n]$) gibt, beginnt sie sofort damit, diese zu sortieren. Während des Sortiervorgangs führt sie eine Folge von Vertauschungen der Form $s[i] \leftrightarrow s[i + 1]$ durch, wobei $i \in \{1, 2, \dots, n - 1\}$ gilt. Am Ende gibt sie die sortierte Zeichenkette zurück und verlangt eine Anzahl an Goldmünzen, die der Summe von $i$ über alle durchgeführten Vertauschungen entspricht (falls eine Vertauschung mehrfach mit demselben $i$ durchgeführt wurde, wird dieses $i$ in der Summe so oft gezählt, wie es vertauscht wurde). Kleopatra ist nicht verschwenderisch: Unter allen Möglichkeiten, die Zeichenkette zu sortieren, wählt sie diejenige, bei der die Anzahl der Münzen, die sie für das Sortieren erhält, minimal ist.

Katharina von Medici liebt ebenfalls Zeichenketten. Sie hat eine Zeichenkette der Länge $n$ und möchte damit spielen. Insbesondere interessiert sie sich für die folgenden Operationen:

  1. "1 i c" — ersetze $s[i]$ durch $c$;
  2. "2 i j" — nimm eine Kopie des Teilstrings von $s$ vom $i$-ten bis einschließlich zum $j$-ten Zeichen ($i \le j$) und sortiere ihn, während die Zeichen der Zeichenkette $s$ unverändert bleiben.
  3. "3 i j" — extrahiere den Teilstring von $s$ vom $i$-ten bis einschließlich zum $j$-ten Zeichen ($i \le j$), sortiere ihn und füge ihn an derselben Position wieder in die Zeichenkette $s$ ein.

Katharina von Medici kann Anfragen des ersten Typs selbst bearbeiten, aber die Anfragen des zweiten und dritten Typs sind zu komplex, weshalb sie sich dafür an Kleopatra wendet. Bei der Berechnung der Kosten dieses Vorgangs summiert Kleopatra nicht die Indizes aus der Zeichenkette $s$ (von $i$ bis $j$), sondern die Indizes relativ zum Anfang des Teilstrings (von $1$ bis $j - i + 1$).

Katharina von Medici ist ebenfalls nicht verschwenderisch und überwacht ihr Budget sorgfältig. Berechne daher für jede ihrer Anfragen an Kleopatra, wie viele Goldmünzen Katharina von Medici ausgeben muss.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $t$ — die Anzahl der Testfälle ($1 \le t \le 3 \cdot 10^5$). Für jeden Testfall gilt:

Die erste Zeile enthält zwei ganze Zahlen $n$ und $q$ — die Länge der Zeichenkette und die Anzahl der Anfragen ($1 \le n, q \le 3 \cdot 10^5$). Die nächste Zeile enthält eine Zeichenkette aus $n$ englischen Großbuchstaben. Die folgenden $q$ Zeilen beschreiben die Anfragen. Jede Anfragebeschreibung hat einen der drei Typen:

  1. "1 i c" — ersetze $s[i]$ durch $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$);
  2. "2 i j" — bestimme die Kosten für das Sortieren des Teilstrings $s[i..j]$, während die Zeichenkette $s$ unverändert bleibt ($1 \le i, j \le n$);
  3. "3 i j" — bestimme die Kosten für das Sortieren des Teilstrings $s[i..j]$, wobei der Teilstring $s[i..j]$ in der Zeichenkette $s$ durch den sortierten ersetzt wird ($1 \le i, j \le n$).

In jedem Testfall gibt es mindestens eine Anfrage vom zweiten oder dritten Typ.

Die Summe von $n$ über alle Testfälle beträgt höchstens $3 \cdot 10^5$. Die Summe von $q$ über alle Testfälle beträgt höchstens $3 \cdot 10^5$.

Ausgabe

Gib für jeden Testfall jeweils in einer eigenen Zeile die Antworten auf alle Anfragen des zweiten und dritten Typs aus, also die Anzahl der Münzen, die Kleopatra für jede der Sortierungen erhält.

Beispiele

Eingabe 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

Ausgabe 1

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

Eingabe 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

Ausgabe 2

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

Hinweis

Betrachten wir das erste Beispiel. Darin lautet die anfängliche Zeichenkette "DBCAA". Gehen wir alle 20 Anfragen der Reihe nach durch:

  1. Anfrage "2 1 5". Aktuelle Zeichenkette: "DBCAA". Teilstring $t[1..5]$ = "DBCAA", Antwort: 18. Die Zeichenkette ändert sich nicht.
  2. Anfrage "2 2 4". Zeichenkette: "DBCAA". Teilstring $t[2..4]$ = "BCA", Antwort: 3. Die Zeichenkette ändert sich nicht.
  3. Anfrage "1 3 Z". Aktualisierung: $t[3] \leftarrow$ "Z". War "DBCAA", jetzt "DBZAA".
  4. Anfrage "2 1 3". Zeichenkette: "DBZAA". Teilstring $t[1..3]$ = "DBZ", Antwort: 1. Die Zeichenkette ändert sich nicht.
  5. Anfrage "3 1 5". Zeichenkette: "DBZAA". Teilstring $t[1..5]$ = "DBZAA", Antwort: 16. Nach der Änderung, Sortieren des Teilstrings: "DBZAA" $\rightarrow$ "AABDZ". Die Zeichenkette wurde zu "AABDZ".
  6. Anfrage "2 1 5". Zeichenkette: "AABDZ". Teilstring "AABDZ", Antwort: 0. Die Zeichenkette ändert sich nicht.
  7. Anfrage "1 5 A". War "AABDZ", jetzt "AABDA".
  8. Anfrage "3 2 4". Zeichenkette: "AABDA". Teilstring $t[2..4]$ = "ABD", Antwort: 0. Nach dem Sortieren ändert sich "ABD" nicht, die Zeichenkette bleibt "AABDA".
  9. Anfrage "2 1 5". Zeichenkette: "AABDA". Teilstring "AABDA", Antwort: 7. Die Zeichenkette ändert sich nicht.
  10. Anfrage "1 1 C". War "AABDA", jetzt "CABDA".
  11. Anfrage "2 1 2". Zeichenkette: "CABDA". Teilstring $t[1..2]$ = "CA", Antwort: 1. Die Zeichenkette ändert sich nicht.
  12. Anfrage "3 4 5". Zeichenkette: "CABDA". Teilstring $t[4..5]$ = "DA", Antwort: 1. Nach der Änderung: "DA" $\rightarrow$ "AD". Die Zeichenkette wurde zu "CABAD".
  13. Anfrage "2 3 5". Zeichenkette: "CABAD". Teilstring $t[3..5]$ = "BAD", Antwort: 1. Die Zeichenkette ändert sich nicht.
  14. Anfrage "1 2 B". War "CABAD", jetzt "CBBAD".
  15. Anfrage "2 1 5". Zeichenkette: "CBBAD". Teilstring "CBBAD", Antwort: 9. Die Zeichenkette ändert sich nicht.
  16. Anfrage "3 1 1". Zeichenkette: "CBBAD". Teilstring $t[1..1]$ = "C", Antwort: 0. Das Sortieren einer Länge von 1 ändert nichts, die Zeichenkette bleibt "CBBAD".
  17. Anfrage "2 1 1". Zeichenkette: "CBBAD". Teilstring $t[1..1]$ = "C", Antwort: 0. Die Zeichenkette ändert sich nicht.
  18. Anfrage "1 4 D". War "CBBAD", jetzt "CBBDD".
  19. Anfrage "2 1 5". Zeichenkette: "CBBDD". Teilstring $t[1..5]$ = "CBBDD", Antwort: 3. Die Zeichenkette ändert sich nicht.
  20. Anfrage "3 1 5". Zeichenkette: "CBBDD". Teilstring $t[1..5]$ = "CBBDD", Antwort: 3. Nach der Änderung: "CBBDD" $\rightarrow$ "BBCDD". Die endgültige Zeichenkette lautet "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.