Universal Cup Judging System

Universal Cup

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

Cléopâtre adore les chaînes de caractères. Lorsqu'on lui donne une chaîne $s$ de longueur $n$ (composée des caractères $s[1], \dots, s[n]$), elle commence immédiatement à la trier. Pendant le processus de tri, elle effectue une séquence d'échanges de la forme $s[i] \leftrightarrow s[i + 1]$, où $i \in \{1, 2, \dots, n - 1\}$. À la fin, elle renvoie la chaîne triée et exige un nombre de pièces d'or égal à la somme des $i$ pour tous les échanges effectués (si un échange a été effectué plusieurs fois avec le même $i$, alors cet indice $i$ sera compté dans la somme autant de fois qu'il a été échangé). Cléopâtre n'est pas dépensière : parmi toutes les façons de trier la chaîne, elle choisit celle où le nombre de pièces qu'elle reçoit pour le tri est minimal.

Catherine de Médicis adore aussi les chaînes de caractères. Elle possède une chaîne de longueur $n$ et souhaite jouer avec. Plus précisément, elle s'intéresse aux opérations suivantes :

  1. "1 i c" — remplacer $s[i]$ par $c$ ;
  2. "2 i j" — prendre une copie de la sous-chaîne de $s$ allant du $i$-ème au $j$-ème caractère inclus ($i \le j$) et la trier, tandis que les caractères de la chaîne $s$ restent inchangés.
  3. "3 i j" — extraire la sous-chaîne de $s$ allant du $i$-ème au $j$-ème caractère inclus ($i \le j$), la trier et la réinsérer dans la chaîne $s$ à la même position.

Catherine de Médicis peut gérer elle-même les requêtes du premier type, mais les requêtes des deuxième et troisième types sont trop complexes et elle s'adresse à Cléopâtre pour les traiter. Lors de l'évaluation du coût de cette procédure, Cléopâtre n'additionne pas les indices de la chaîne $s$ (de $i$ à $j$), mais les indices relatifs au début de la sous-chaîne (de $1$ à $j - i + 1$).

Catherine de Médicis n'est pas dépensière non plus et surveille attentivement son budget. Par conséquent, pour chacune de ses demandes à Cléopâtre, calculez combien de pièces d'or Catherine de Médicis devra dépenser.

Entrée

La première ligne de l'entrée contient un entier $t$ — le nombre de cas de test ($1 \le t \le 3 \cdot 10^5$). Pour chaque cas de test :

La première ligne contient deux entiers, $n$ et $q$ — la longueur de la chaîne et le nombre de requêtes ($1 \le n, q \le 3 \cdot 10^5$). La ligne suivante contient une chaîne de $n$ lettres majuscules de l'alphabet anglais. Les $q$ lignes suivantes décrivent les requêtes. Chaque description de requête est de l'un des trois types :

  1. "1 i c" — remplacer $s[i]$ par $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$) ;
  2. "2 i j" — trouver le coût du tri de la sous-chaîne $s[i..j]$, tandis que la chaîne $s$ reste inchangée ($1 \le i, j \le n$) ;
  3. "3 i j" — trouver le coût du tri de la sous-chaîne $s[i..j]$, tandis que la sous-chaîne $s[i..j]$ dans la chaîne $s$ est remplacée par la sous-chaîne triée ($1 \le i, j \le n$).

Dans chaque cas de test, il y aura au moins une requête du deuxième ou du troisième type.

La somme de $n$ sur l'ensemble des cas de test est d'au plus $3 \cdot 10^5$. La somme de $q$ sur l'ensemble des cas de test est d'au plus $3 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez sur une ligne séparée les réponses à toutes les requêtes des deuxième et troisième types, c'est-à-dire le nombre de pièces que Cléopâtre recevra pour chacun des tris.

Exemples

Entrée 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

Sortie 1

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

Entrée 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

Sortie 2

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

Note

Considérons le premier exemple. Dans celui-ci, la chaîne initiale est "DBCAA". Parcourons les 20 requêtes dans l'ordre :

  1. Requête "2 1 5". Chaîne actuelle: "DBCAA". Sous-chaîne $t[1..5]$ = "DBCAA", réponse: 18. La chaîne ne change pas.
  2. Requête "2 2 4". Chaîne: "DBCAA". Sous-chaîne $t[2..4]$ = "BCA", réponse: 3. La chaîne ne change pas.
  3. Requête "1 3 Z". Mise à jour: $t[3] \leftarrow$ "Z". Était "DBCAA", maintenant "DBZAA".
  4. Requête "2 1 3". Chaîne: "DBZAA". Sous-chaîne $t[1..3]$ = "DBZ", réponse: 1. La chaîne ne change pas.
  5. Requête "3 1 5". Chaîne: "DBZAA". Sous-chaîne $t[1..5]$ = "DBZAA", réponse: 16. Après mutation, tri de la sous-chaîne : "DBZAA" $\rightarrow$ "AABDZ". La chaîne est devenue "AABDZ".
  6. Requête "2 1 5". Chaîne: "AABDZ". Sous-chaîne "AABDZ", réponse: 0. La chaîne ne change pas.
  7. Requête "1 5 A". Était "AABDZ", maintenant "AABDA".
  8. Requête "3 2 4". Chaîne: "AABDA". Sous-chaîne $t[2..4]$ = "ABD", réponse: 0. Après le tri, "ABD" ne change pas, la chaîne reste "AABDA".
  9. Requête "2 1 5". Chaîne: "AABDA". Sous-chaîne "AABDA", réponse: 7. La chaîne ne change pas.
  10. Requête "1 1 C". Était "AABDA", maintenant "CABDA".
  11. Requête "2 1 2". Chaîne: "CABDA". Sous-chaîne $t[1..2]$ = "CA", réponse: 1. La chaîne ne change pas.
  12. Requête "3 4 5". Chaîne: "CABDA". Sous-chaîne $t[4..5]$ = "DA", réponse: 1. Après mutation : "DA" $\rightarrow$ "AD". La chaîne est devenue "CABAD".
  13. Requête "2 3 5". Chaîne: "CABAD". Sous-chaîne $t[3..5]$ = "BAD", réponse: 1. La chaîne ne change pas.
  14. Requête "1 2 B". Était "CABAD", maintenant "CBBAD".
  15. Requête "2 1 5". Chaîne: "CBBAD". Sous-chaîne "CBBAD", réponse: 9. La chaîne ne change pas.
  16. Requête "3 1 1". Chaîne: "CBBAD". Sous-chaîne $t[1..1]$ = "C", réponse: 0. Trier une longueur de 1 ne change rien, la chaîne reste "CBBAD".
  17. Requête "2 1 1". Chaîne: "CBBAD". Sous-chaîne $t[1..1]$ = "C", réponse: 0. La chaîne ne change pas.
  18. Requête "1 4 D". Était "CBBAD", maintenant "CBBDD".
  19. Requête "2 1 5". Chaîne: "CBBDD". Sous-chaîne $t[1..5]$ = "CBBDD", réponse: 3. La chaîne ne change pas.
  20. Requête "3 1 5". Chaîne: "CBBDD". Sous-chaîne $t[1..5]$ = "CBBDD", réponse: 3. Après mutation : "CBBDD" $\rightarrow$ "BBCDD". La chaîne finale est "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.