Universal Cup Judging System

Universal Cup

Süre Sınırı: 5.5 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Cleopatra ama le stringhe. Quando le viene data una stringa $s$ di lunghezza $n$ (composta dai caratteri $s[1], \dots, s[n]$), inizia immediatamente a ordinarla. Durante il processo di ordinamento, esegue una sequenza di scambi della forma $s[i] \leftrightarrow s[i + 1]$, dove $i \in \{1, 2, \dots, n - 1\}$. Alla fine, restituisce la stringa ordinata e pretende un numero di monete d'oro pari alla somma di $i$ per tutti gli scambi effettuati (se uno scambio è stato effettuato più volte con lo stesso $i$, allora quell'$i$ verrà contato nella somma tante volte quante è stato scambiato). Cleopatra non è sprecona: tra tutti i modi per ordinare la stringa, sceglie quello in cui il numero di monete che riceve per l'ordinamento è minimo.

Anche Caterina de' Medici ama le stringhe. Ha una stringa di lunghezza $n$ e vuole giocarci. In particolare, è interessata alle seguenti operazioni:

  1. "1 i c" — sostituire $s[i]$ con $c$;
  2. "2 i j" — prendere una copia della sottostringa di $s$ dall'$i$-esimo al $j$-esimo carattere inclusi ($i \le j$) e ordinarla, mentre i caratteri della stringa $s$ rimangono invariati.
  3. "3 i j" — estrarre la sottostringa di $s$ dall'$i$-esimo al $j$-esimo carattere inclusi ($i \le j$), ordinarla e reinserirla nella stringa $s$ nella stessa posizione.

Caterina de' Medici può gestire da sola le query del primo tipo, ma le query del secondo e del terzo tipo sono troppo complesse e per quelle si rivolgerà a Cleopatra. Nel valutare il costo di questa procedura, Cleopatra sommerà non gli indici della stringa $s$ (da $i$ a $j$), bensì gli indici relativi all'inizio della sottostringa (da $1$ a $j - i + 1$).

Anche Caterina de' Medici non è sprecona e controlla attentamente il suo budget. Pertanto, per ciascuna delle sue richieste a Cleopatra, calcola quante monete d'oro dovrà spendere Caterina de' Medici.

Input

La prima riga dell'input contiene un intero $t$ — il numero di casi di test ($1 \le t \le 3 \cdot 10^5$). Per ciascun caso di test:

La prima riga contiene due interi, $n$ e $q$ — la lunghezza della stringa e il numero di query ($1 \le n, q \le 3 \cdot 10^5$). La riga successiva contiene una stringa di $n$ lettere maiuscole dell'alfabeto inglese. Le seguenti $q$ righe descrivono le query. Ogni descrizione di query appartiene a uno dei tre tipi:

  1. "1 i c" — sostituire $s[i]$ con $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$);
  2. "2 i j" — trovare il costo per ordinare la sottostringa $s[i..j]$, mentre la stringa $s$ rimane invariata ($1 \le i, j \le n$);
  3. "3 i j" — trovare il costo per ordinare la sottostringa $s[i..j]$, mentre la sottostringa $s[i..j]$ nella stringa $s$ viene sostituita con quella ordinata ($1 \le i, j \le n$).

In ciascun caso di test ci sarà almeno una query del secondo o del terzo tipo.

La somma di $n$ su tutti i casi di test è al massimo $3 \cdot 10^5$. La somma di $q$ su tutti i casi di test è al massimo $3 \cdot 10^5$.

Output

Per ciascun caso di test, stampa su righe separate le risposte a tutte le query del secondo e del terzo tipo, ossia il numero di monete che Cleopatra riceverà per ciascuno degli ordinamenti.

Esempi

Input 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

Output 1

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

Input 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

Output 2

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

Note

Consideriamo il primo esempio. In esso, la stringa iniziale è "DBCAA". Esaminiamo tutte le 20 query in ordine:

  1. Query "2 1 5". Stringa corrente: "DBCAA". Sottostringa $t[1..5]$ = "DBCAA", risposta: 18. La stringa non cambia.
  2. Query "2 2 4". Stringa: "DBCAA". Sottostringa $t[2..4]$ = "BCA", risposta: 3. La stringa non cambia.
  3. Query "1 3 Z". Aggiornamento: $t[3] \leftarrow$ "Z". Era "DBCAA", ora è "DBZAA".
  4. Query "2 1 3". Stringa: "DBZAA". Sottostringa $t[1..3]$ = "DBZ", risposta: 1. La stringa non cambia.
  5. Query "3 1 5". Stringa: "DBZAA". Sottostringa $t[1..5]$ = "DBZAA", risposta: 16. Dopo la modifica, ordinando la sottostringa: "DBZAA" $\rightarrow$ "AABDZ". La stringa è diventata "AABDZ".
  6. Query "2 1 5". Stringa: "AABDZ". Sottostringa "AABDZ", risposta: 0. La stringa non cambia.
  7. Query "1 5 A". Era "AABDZ", ora è "AABDA".
  8. Query "3 2 4". Stringa: "AABDA". Sottostringa $t[2..4]$ = "ABD", risposta: 0. Dopo l'ordinamento "ABD" non cambia, la stringa rimane "AABDA".
  9. Query "2 1 5". Stringa: "AABDA". Sottostringa "AABDA", risposta: 7. La stringa non cambia.
  10. Query "1 1 C". Era "AABDA", ora è "CABDA".
  11. Query "2 1 2". Stringa: "CABDA". Sottostringa $t[1..2]$ = "CA", risposta: 1. La stringa non cambia.
  12. Query "3 4 5". Stringa: "CABDA". Sottostringa $t[4..5]$ = "DA", risposta: 1. Dopo la modifica: "DA" $\rightarrow$ "AD". La stringa è diventata "CABAD".
  13. Query "2 3 5". Stringa: "CABAD". Sottostringa $t[3..5]$ = "BAD", risposta: 1. La stringa non cambia.
  14. Query "1 2 B". Era "CABAD", ora è "CBBAD".
  15. Query "2 1 5". Stringa: "CBBAD". Sottostringa "CBBAD", risposta: 9. La stringa non cambia.
  16. Query "3 1 1". Stringa: "CBBAD". Sottostringa $t[1..1]$ = "C", risposta: 0. Ordinare una lunghezza pari a 1 non cambia nulla, la stringa rimane "CBBAD".
  17. Query "2 1 1". Stringa: "CBBAD". Sottostringa $t[1..1]$ = "C", risposta: 0. La stringa non cambia.
  18. Query "1 4 D". Era "CBBAD", ora è "CBBDD".
  19. Query "2 1 5". Stringa: "CBBDD". Sottostringa $t[1..5]$ = "CBBDD", risposta: 3. La stringa non cambia.
  20. Query "3 1 5". Stringa: "CBBDD". Sottostringa $t[1..5]$ = "CBBDD", risposta: 3. Dopo la modifica: "CBBDD" $\rightarrow$ "BBCDD". La stringa finale è "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.