Universal Cup Judging System

Universal Cup

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

A Cleopatra le encantan las cadenas. Cuando le dan una cadena $s$ de longitud $n$ (compuesta por los caracteres $s[1], \dots, s[n]$), inmediatamente comienza a ordenarla. Durante el proceso de ordenamiento, realiza una secuencia de intercambios de la forma $s[i] \leftrightarrow s[i + 1]$, donde $i \in \{1, 2, \dots, n - 1\}$. Al final, devuelve la cadena ordenada y exige una cantidad de monedas de oro igual a la suma de $i$ para todos los intercambios realizados (si un intercambio se realizó múltiples veces con el mismo $i$, entonces ese $i$ se contará en la suma tantas veces como se haya intercambiado). Cleopatra no es derrochadora: entre todas las formas de ordenar la cadena, elige aquella en la que el número de monedas que recibe por ordenar es mínimo.

A Catalina de Médici también le encantan las cadenas. Tiene una cadena de longitud $n$ y quiere jugar con ella. Específicamente, está interesada en las siguientes operaciones:

  1. "1 i c" — reemplazar $s[i]$ por $c$;
  2. "2 i j" — tomar una copia de la subcadena de $s$ desde el $i$-ésimo hasta el $j$-ésimo carácter inclusive ($i \le j$) y ordenarla, mientras que los caracteres de la cadena $s$ permanecen sin cambios.
  3. "3 i j" — extraer la subcadena de $s$ desde el $i$-ésimo hasta el $j$-ésimo carácter inclusive ($i \le j$), ordenarla e insertarla de nuevo en la cadena $s$ en la misma posición.

Catalina de Médici puede encargarse ella misma de las consultas del primer tipo, pero las consultas del segundo y tercer tipo son demasiado complejas y acudirá a Cleopatra para realizarlas. Al evaluar el costo de este procedimiento, Cleopatra sumará no los índices de la cadena $s$ (de $i$ a $j$), sino los índices relativos al comienzo de la subcadena (de $1$ a $j - i + 1$).

Catalina de Médici tampoco es derrochadora y supervisa cuidadosamente su presupuesto. Por lo tanto, para cada una de sus solicitudes a Cleopatra, calcula cuántas monedas de oro tendrá que gastar Catalina de Médici.

Entrada

La primera línea de la entrada contiene un entero $t$ — el número de casos de prueba ($1 \le t \le 3 \cdot 10^5$). Para cada caso de prueba:

La primera línea contiene dos enteros, $n$ y $q$ — la longitud de la cadena y el número de consultas ($1 \le n, q \le 3 \cdot 10^5$). La siguiente línea contiene una cadena de $n$ letras inglesas mayúsculas. Las siguientes $q$ líneas describen las consultas. Cada descripción de consulta tiene uno de los tres tipos:

  1. "1 i c" — reemplazar $s[i]$ por $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$);
  2. "2 i j" — hallar el costo de ordenar la subcadena $s[i..j]$, mientras la cadena $s$ permanece sin cambios ($1 \le i, j \le n$);
  3. "3 i j" — hallar el costo de ordenar la subcadena $s[i..j]$, mientras la subcadena $s[i..j]$ en la cadena $s$ se reemplaza por la subcadena ordenada ($1 \le i, j \le n$).

En cada caso de prueba habrá al menos una consulta del segundo o tercer tipo.

La suma de $n$ en todos los casos de prueba es a lo sumo $3 \cdot 10^5$. La suma de $q$ en todos los casos de prueba es a lo sumo $3 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime en una línea separada las respuestas a todas las consultas del segundo y tercer tipo, es decir, el número de monedas que recibirá Cleopatra por cada uno de los ordenamientos.

Ejemplos

Entrada 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

Salida 1

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

Entrada 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

Salida 2

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

Nota

Consideremos el primer ejemplo. En él, la cadena inicial es "DBCAA". Repasemos las 20 consultas en orden:

  1. Consulta "2 1 5". Cadena actual: "DBCAA". Subcadena $t[1..5]$ = "DBCAA", respuesta: 18. La cadena no cambia.
  2. Consulta "2 2 4". Cadena: "DBCAA". Subcadena $t[2..4]$ = "BCA", respuesta: 3. La cadena no cambia.
  3. Consulta "1 3 Z". Actualización: $t[3] \leftarrow$ "Z". Era "DBCAA", ahora es "DBZAA".
  4. Consulta "2 1 3". Cadena: "DBZAA". Subcadena $t[1..3]$ = "DBZ", respuesta: 1. La cadena no cambia.
  5. Consulta "3 1 5". Cadena: "DBZAA". Subcadena $t[1..5]$ = "DBZAA", respuesta: 16. Tras la mutación, ordenando la subcadena: "DBZAA" $\rightarrow$ "AABDZ". La cadena pasó a ser "AABDZ".
  6. Consulta "2 1 5". Cadena: "AABDZ". Subcadena "AABDZ", respuesta: 0. La cadena no cambia.
  7. Consulta "1 5 A". Era "AABDZ", ahora es "AABDA".
  8. Consulta "3 2 4". Cadena: "AABDA". Subcadena $t[2..4]$ = "ABD", respuesta: 0. Tras ordenar, "ABD" no cambia, la cadena sigue siendo "AABDA".
  9. Consulta "2 1 5". Cadena: "AABDA". Subcadena "AABDA", respuesta: 7. La cadena no cambia.
  10. Consulta "1 1 C". Era "AABDA", ahora es "CABDA".
  11. Consulta "2 1 2". Cadena: "CABDA". Subcadena $t[1..2]$ = "CA", respuesta: 1. La cadena no cambia.
  12. Consulta "3 4 5". Cadena: "CABDA". Subcadena $t[4..5]$ = "DA", respuesta: 1. Tras la mutación: "DA" $\rightarrow$ "AD". La cadena pasó a ser "CABAD".
  13. Consulta "2 3 5". Cadena: "CABAD". Subcadena $t[3..5]$ = "BAD", respuesta: 1. La cadena no cambia.
  14. Consulta "1 2 B". Era "CABAD", ahora es "CBBAD".
  15. Consulta "2 1 5". Cadena: "CBBAD". Subcadena "CBBAD", respuesta: 9. La cadena no cambia.
  16. Consulta "3 1 1". Cadena: "CBBAD". Subcadena $t[1..1]$ = "C", respuesta: 0. Ordenar una longitud de 1 no cambia nada, la cadena sigue siendo "CBBAD".
  17. Consulta "2 1 1". Cadena: "CBBAD". Subcadena $t[1..1]$ = "C", respuesta: 0. La cadena no cambia.
  18. Consulta "1 4 D". Era "CBBAD", ahora es "CBBDD".
  19. Consulta "2 1 5". Cadena: "CBBDD". Subcadena $t[1..5]$ = "CBBDD", respuesta: 3. La cadena no cambia.
  20. Consulta "3 1 5". Cadena: "CBBDD". Subcadena $t[1..5]$ = "CBBDD", respuesta: 3. Tras la mutación: "CBBDD" $\rightarrow$ "BBCDD". La cadena final es "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.