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

Kleópatra elskar strengi. Þegar henni er gefinn strengur $s$ af lengd $n$ (sem samanstendur af stöfunum $s[1], \dots, s[n]$) byrjar hún strax að raða honum. Í röðunarferlinu framkvæmir hún runu af víxlunum á forminu $s[i] \leftrightarrow s[i + 1]$, þar sem $i \in \{1, 2, \dots, n - 1\}$. Að lokum skilar hún raðaða strengnum og krefst fjölda gullpeninga sem jafngildir summu $i$ fyrir allar víxlanirnar sem gerðar voru (ef víxlun var gerðнта oftar en einu sinni með sama $i$, þá telst það $i$ með í summunni jafn oft og víxlað var). Kleópatra er ekki eyðslusöm: af öllum leiðum til að raða strengnum velur hún þá leið þar sem fjöldi peninga sem hún fær fyrir röðunina er í lágmarki.

Katrín af Medici elskar líka strengi. Hún á streng af lengd $n$ og vill leika sér með hann. Nánar tiltekið hefur hún áhuga á eftirfarandi aðgerðum:

  1. "1 i c" — skipta $s[i]$ út fyrir $c$;
  2. "2 i j" — taka afrit af hlutstreng $s$ frá $i$-ta staf til $j$-ta stafs að báðum meðtöldum ($i \le j$) og raða honum, á meðan stafir strengsins $s$ haldast óbreyttir.
  3. "3 i j" — taka hlutstreng $s$ frá $i$-ta staf til $j$-ta stafs að báðum meðtöldum ($i \le j$), raða honum og setja hann aftur inn í strenginn $s$ á sama stað.

Katrín af Medici getur séð um fyrirspurnir af fyrstu gerðinni sjálf, en fyrirspurnir af annarri og þriðju gerð eru of flóknar og mun hún leita til Kleópötru með þær. Þegar kostnaðurinn við þetta ferli er metinn mun Kleópatra ekki leggja saman vísana úr strengnum $s$ (frá $i$ til $j$), heldur vísana miðað við upphaf hlutstrengsins (frá $1$ til $j - i + 1$).

Katrín af Medici er heldur ekki eyðslusöm og fylgist grannt með fjárhagsáætlun sinni. Reiknaðu því fyrir hverja beiðni hennar til Kleópötru hversu mörgum gullpeningum Katrín af Medici þarf að eyða.

Inntak

Fyrsta lína inntaksins inniheldur heiltölu $t$ — fjölda prófunartilvika ($1 \le t \le 3 \cdot 10^5$). Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur tvær heiltölur, $n$ og $q$ — lengd strengsins og fjölda fyrirspurna ($1 \le n, q \le 3 \cdot 10^5$). Næsta lína inniheldur streng af $n$ enskum hástöfum. Næstu $q$ línur lýsa fyrirspurnunum. Hver fyrirspurnarlýsing er af einni af þremur gerðum:

  1. "1 i c" — skipta $s[i]$ út fyrir $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$);
  2. "2 i j" — finna kostnaðinn við að raða hlutstrengnum $s[i..j]$, á meðan strengurinn $s$ helst óbreyttur ($1 \le i, j \le n$);
  3. "3 i j" — finna kostnaðinn við að raða hlutstrengnum $s[i..j]$, á meðan hlutstrengnum $s[i..j]$ í strengnum $s$ er skipt út fyrir þann raðaða ($1 \le i, j \le n$).

Í hverju prófunartilviki verður að minnsta kosti ein fyrirspurn af annarri eða þriðju gerð.

Summa $n$ yfir öll prófunartilvik er í mesta lagi $3 \cdot 10^5$. Summa $q$ yfir öll prófunartilvik er í mesta lagi $3 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta í sérstökum línum svörin við öllum fyrirspurnum af annarri og þriðju gerð, það er fjölda peninga sem Kleópatra fær fyrir hverja röðun.

Dæmi

Inntak 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

Úttak 1

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

Inntak 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

Úttak 2

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

Athugasemd

Skoðum fyrsta dæmið. Í því er upphafsstrengurinn "DBCAA". Förum í gegnum allar 20 fyrirspurnirnar í röð:

  1. Fyrirspurn "2 1 5". Núverandi strengur: "DBCAA". Hlutstrengur $t[1..5]$ = "DBCAA", svar: 18. Strengurinn breytist ekki.
  2. Fyrirspurn "2 2 4". Strengur: "DBCAA". Hlutstrengur $t[2..4]$ = "BCA", svar: 3. Strengurinn breytist ekki.
  3. Fyrirspurn "1 3 Z". Uppfærsla: $t[3] \leftarrow$ "Z". Var "DBCAA", nú "DBZAA".
  4. Fyrirspurn "2 1 3". Strengur: "DBZAA". Hlutstrengur $t[1..3]$ = "DBZ", svar: 1. Strengurinn breytist ekki.
  5. Fyrirspurn "3 1 5". Strengur: "DBZAA". Hlutstrengur $t[1..5]$ = "DBZAA", svar: 16. Eftir breytingu, röðun hlutstrengsins: "DBZAA" $\rightarrow$ "AABDZ". Strengurinn varð "AABDZ".
  6. Fyrirspurn "2 1 5". Strengur: "AABDZ". Hlutstrengur "AABDZ", svar: 0. Strengurinn breytist ekki.
  7. Fyrirspurn "1 5 A". Var "AABDZ", nú "AABDA".
  8. Fyrirspurn "3 2 4". Strengur: "AABDA". Hlutstrengur $t[2..4]$ = "ABD", svar: 0. Eftir röðun breytist "ABD" ekki, strengurinn helst "AABDA".
  9. Fyrirspurn "2 1 5". Strengur: "AABDA". Hlutstrengur "AABDA", svar: 7. Strengurinn breytist ekki.
  10. Fyrirspurn "1 1 C". Var "AABDA", nú "CABDA".
  11. Fyrirspurn "2 1 2". Strengur: "CABDA". Hlutstrengur $t[1..2]$ = "CA", svar: 1. Strengurinn breytist ekki.
  12. Fyrirspurn "3 4 5". Strengur: "CABDA". Hlutstrengur $t[4..5]$ = "DA", svar: 1. Eftir breytingu: "DA" $\rightarrow$ "AD". Strengurinn varð "CABAD".
  13. Fyrirspurn "2 3 5". Strengur: "CABAD". Hlutstrengur $t[3..5]$ = "BAD", svar: 1. Strengurinn breytist ekki.
  14. Fyrirspurn "1 2 B". Var "CABAD", nú "CBBAD".
  15. Fyrirspurn "2 1 5". Strengur: "CBBAD". Hlutstrengur "CBBAD", svar: 9. Strengurinn breytist ekki.
  16. Fyrirspurn "3 1 1". Strengur: "CBBAD". Hlutstrengur $t[1..1]$ = "C", svar: 0. Að raða lengd 1 breytir engu, strengurinn helst "CBBAD".
  17. Fyrirspurn "2 1 1". Strengur: "CBBAD". Hlutstrengur $t[1..1]$ = "C", svar: 0. Strengurinn breytist ekki.
  18. Fyrirspurn "1 4 D". Var "CBBAD", nú "CBBDD".
  19. Fyrirspurn "2 1 5". Strengur: "CBBDD". Hlutstrengur $t[1..5]$ = "CBBDD", svar: 3. Strengurinn breytist ekki.
  20. Fyrirspurn "3 1 5". Strengur: "CBBDD". Hlutstrengur $t[1..5]$ = "CBBDD", svar: 3. Eftir breytingu: "CBBDD" $\rightarrow$ "BBCDD". Lokastrengurinn er "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.