Universal Cup Judging System

Universal Cup

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

Kleopatra älskar strängar. När hon får en sträng $s$ av längd $n$ (bestående av tecknen $s[1], \dots, s[n]$) börjar hon genast sortera den. Under sorteringsprocessen utför hon en sekvens av byten på formen $s[i] \leftrightarrow s[i + 1]$, där $i \in \{1, 2, \dots, n - 1\}$. Till slut returnerar hon den sorterade strängen och kräver ett antal guldmynt som är lika med summan av $i$ för alla utförda byten (om ett byte utfördes flera gånger med samma $i$, räknas detta $i$ med i summan lika många gånger som det byttes). Kleopatra är inte slösaktig: bland alla sätt att sortera strängen väljer hon det där antalet mynt hon får för sorteringen är minimalt.

Katarina av Medici älskar också strängar. Hon har en sträng av längd $n$ och vill leka med den. Specifikt är hon intresserad av följande operationer:

  1. "1 i c" — ersätt $s[i]$ med $c$;
  2. "2 i j" — ta en kopia av delsträngen av $s$ från det $i$-te till och med det $j$-te tecknet ($i \le j$) och sortera den, medan tecknen i strängen $s$ förblir oförändrade.
  3. "3 i j" — plocka ut delsträngen av $s$ från det $i$-te till och med det $j$-te tecknet ($i \le j$), sortera den och sätt tillbaka den i strängen $s$ på samma plats.

Katarina av Medici kan hantera frågor av den första typen själv, men frågor av den andra och tredje typen är för komplicerade, så för dem vänder hon sig till Kleopatra. När Kleopatra beräknar kostnaden för denna procedur summerar hon inte indexen från strängen $s$ (från $i$ till $j$), utan indexen relativt delsträngens början (från $1$ till $j - i + 1$).

Katarina av Medici är inte heller slösaktig och övervakar noggrant sin budget. Beräkna därför för var och en av hennes förfrågningar till Kleopatra hur många guldmynt Katarina av Medici kommer att behöva betala.

Indata

Den första raden i indata innehåller ett heltal $t$ — antalet testfall ($1 \le t \le 3 \cdot 10^5$). För varje testfall gäller:

Den första raden innehåller två heltal, $n$ och $q$ — strängens längd och antalet frågor ($1 \le n, q \le 3 \cdot 10^5$). Nästa rad innehåller en sträng med $n$ stora engelska bokstäver. De följande $q$ raderna beskriver frågorna. Varje frågebeskrivning har en av de tre typerna:

  1. "1 i c" — ersätt $s[i]$ med $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$);
  2. "2 i j" — bestäm kostnaden för att sortera delsträngen $s[i..j]$, medan strängen $s$ förblir oförändrad ($1 \le i, j \le n$);
  3. "3 i j" — bestäm kostnaden för att sortera delsträngen $s[i..j]$, samtidigt som delsträngen $s[i..j]$ i strängen $s$ ersätts med den sorterade ($1 \le i, j \le n$).

I varje testfall kommer det att finnas minst en fråga av den andra eller tredje typen.

Summan av $n$ över alla testfall är högst $3 \cdot 10^5$. Summan av $q$ över alla testfall är högst $3 \cdot 10^5$.

Utdata

För varje testfall, skriv på separata rader ut svaren på alla frågor av den andra och tredje typen, det vill säga antalet mynt som Kleopatra kommer att få för var och en av sorteringarna.

Exempel

Indata 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

Utdata 1

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

Indata 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

Utdata 2

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

Anmärkning

Betrakta det första exemplet. I det är startsträngen "DBCAA". Låt oss gå igenom alla 20 frågor i ordning:

  1. Fråga "2 1 5". Aktuell sträng: "DBCAA". Delsträng $t[1..5]$ = "DBCAA", svar: 18. Strängen ändras inte.
  2. Fråga "2 2 4". Sträng: "DBCAA". Delsträng $t[2..4]$ = "BCA", svar: 3. Strängen ändras inte.
  3. Fråga "1 3 Z". Uppdatering: $t[3] \leftarrow$ "Z". Var "DBCAA", nu "DBZAA".
  4. Fråga "2 1 3". Sträng: "DBZAA". Delsträng $t[1..3]$ = "DBZ", svar: 1. Strängen ändras inte.
  5. Fråga "3 1 5". Sträng: "DBZAA". Delsträng $t[1..5]$ = "DBZAA", svar: 16. Efter ändring, sortering av delsträngen: "DBZAA" $\rightarrow$ "AABDZ". Strängen blev "AABDZ".
  6. Fråga "2 1 5". Sträng: "AABDZ". Delsträng "AABDZ", svar: 0. Strängen ändras inte.
  7. Fråga "1 5 A". Var "AABDZ", nu "AABDA".
  8. Fråga "3 2 4". Sträng: "AABDA". Delsträng $t[2..4]$ = "ABD", svar: 0. Efter sortering ändras inte "ABD", strängen förblir "AABDA".
  9. Fråga "2 1 5". Sträng: "AABDA". Delsträng "AABDA", svar: 7. Strängen ändras inte.
  10. Fråga "1 1 C". Var "AABDA", nu "CABDA".
  11. Fråga "2 1 2". Sträng: "CABDA". Delsträng $t[1..2]$ = "CA", svar: 1. Strängen ändras inte.
  12. Fråga "3 4 5". Sträng: "CABDA". Delsträng $t[4..5]$ = "DA", svar: 1. Efter ändring: "DA" $\rightarrow$ "AD". Strängen blev "CABAD".
  13. Fråga "2 3 5". Sträng: "CABAD". Delsträng $t[3..5]$ = "BAD", svar: 1. Strängen ändras inte.
  14. Fråga "1 2 B". Var "CABAD", nu "CBBAD".
  15. Fråga "2 1 5". Sträng: "CBBAD". Delsträng "CBBAD", svar: 9. Strängen ändras inte.
  16. Fråga "3 1 1". Sträng: "CBBAD". Delsträng $t[1..1]$ = "C", svar: 0. Att sortera längd 1 ändrar ingenting, strängen förblir "CBBAD".
  17. Fråga "2 1 1". Sträng: "CBBAD". Delsträng $t[1..1]$ = "C", svar: 0. Strängen ändras inte.
  18. Fråga "1 4 D". Var "CBBAD", nu "CBBDD".
  19. Fråga "2 1 5". Sträng: "CBBDD". Delsträng $t[1..5]$ = "CBBDD", svar: 3. Strängen ändras inte.
  20. Fråga "3 1 5". Sträng: "CBBDD". Delsträng $t[1..5]$ = "CBBDD", svar: 3. Efter ändring: "CBBDD" $\rightarrow$ "BBCDD". Den slutliga strängen är "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.