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 好鍾意字串。當佢收到一個長度為 $n$ 嘅字串 $s$(由字符 $s[1], \dots, s[n]$ 組成)嗰陣,佢會即刻開始將佢排序。喺排序過程入面,佢會執行一連串形如 $s[i] \leftrightarrow s[i + 1]$ 嘅交換操作,其中 $i \in \{1, 2, \dots, n - 1\}$。最後,佢會交還排好序嘅字串,並要求等同於所有執行過嘅交換操作入面 $i$ 嘅總和咁多枚金幣(如果同一個 $i$ 交換咗多次,咁呢個 $i$ 喺總和入面就會被計算相應咁多次)。Cleopatra 唔會浪費:喺所有可以將字串排序嘅方法入面,佢會揀令佢收到最少金幣嗰種。

Catherine de' Medici 都好鍾意字串。佢有一個長度為 $n$ 嘅字串,而且想同佢玩遊戲。具體嚟講,佢對以下操作感興趣:

  1. "1 i c" —— 將 $s[i]$ 替換為 $c$;
  2. "2 i j" —— 複製字串 $s$ 由第 $i$ 個到第 $j$ 個字符(包括兩端)嘅子串($i \le j$)並將佢排序,而字串 $s$ 本身嘅字符保持唔變。
  3. "3 i j" —— 取出字串 $s$ 由第 $i$ 個到第 $j$ 個字符(包括兩端)嘅子串($i \le j$),將佢排序,然後插返入字串 $s$ 嘅同一個位置。

Catherine de' Medici 可以自己處理第一種詢問,但係第二種同第三種詢問太複雜,佢會去搵 Cleopatra 幫手。喺計算呢個過程嘅費用時,Cleopatra 累加嘅唔係字串 $s$ 入面嘅下標(由 $i$ 到 $j$),而係相對於子串開頭嘅下標(由 $1$ 到 $j - i + 1$)。

Catherine de' Medici 亦都好慳家,會仔細監察自己嘅預算。因此,對於佢向 Cleopatra 提出嘅每一個請求,請計算 Catherine de' Medici 需要花費幾多枚金幣。

輸入格式

輸入第一行包含一個整數 $t$ —— 測試數據組數($1 \le t \le 3 \cdot 10^5$)。對於每組測試數據:

第一行包含兩個整數 $n$ 同 $q$ —— 字串嘅長度同埋詢問嘅數量($1 \le n, q \le 3 \cdot 10^5$)。下一行包含一個由 $n$ 個大寫英文字母組成嘅字串。接下來 $q$ 行描述各個詢問。每個詢問嘅描述屬於以下三種之一:

  1. "1 i c" —— 將 $s[i]$ 替換為 $c$($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$);
  2. "2 i j" —— 求將子串 $s[i..j]$ 排序嘅費用,同時字串 $s$ 保持唔變($1 \le i, j \le n$);
  3. "3 i j" —— 求將子串 $s[i..j]$ 排序嘅費用,同時字串 $s$ 入面嘅子串 $s[i..j]$ 被替換成排好序嘅子串($1 \le i, j \le n$)。

喺每組測試數據入面,至少會有一個第二種或者第三種嘅詢問。

所有測試數據入面 $n$ 嘅總和唔超過 $3 \cdot 10^5$。所有測試數據入面 $q$ 嘅總和唔超過 $3 \cdot 10^5$。

輸出格式

對於每組測試數據,喺獨立嘅行入面輸出所有第二種同第三種詢問嘅答案,即係 Cleopatra 每次排序會收到嘅金幣數量。

範例

範例輸入 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

範例輸出 1

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

範例輸入 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

範例輸出 2

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

備註

考慮第一個範例。喺呢個範例入面,初始字串係 "DBCAA"。等我哋按順序睇下全部 20 個詢問:

  1. 詢問 "2 1 5". 當前字串: "DBCAA". 子串 $t[1..5]$ = "DBCAA", 答案: 18. 字串保持唔變。
  2. 詢問 "2 2 4". 字串: "DBCAA". 子串 $t[2..4]$ = "BCA", 答案: 3. 字串保持唔變。
  3. 詢問 "1 3 Z". 更新: $t[3] \leftarrow$ "Z". 原本係 "DBCAA",而家係 "DBZAA"。
  4. 詢問 "2 1 3". 字串: "DBZAA". 子串 $t[1..3]$ = "DBZ", 答案: 1. 字串保持唔變。
  5. 詢問 "3 1 5". 字串: "DBZAA". 子串 $t[1..5]$ = "DBZAA", 答案: 16. 變化之後,對子串排序:"DBZAA" $\rightarrow$ "AABDZ"。字串變成 "AABDZ"。
  6. 詢問 "2 1 5". 字串: "AABDZ". 子串 "AABDZ", 答案: 0. 字串保持唔變。
  7. 詢問 "1 5 A". 原本係 "AABDZ",而家係 "AABDA"。
  8. 詢問 "3 2 4". 字串: "AABDA". 子串 $t[2..4]$ = "ABD", 答案: 0. 排序之後 "ABD" 冇變,字串維持係 "AABDA"。
  9. 詢問 "2 1 5". 字串: "AABDA". 子串 "AABDA", 答案: 7. 字串保持唔變。
  10. 詢問 "1 1 C". 原本係 "AABDA",而家係 "CABDA"。
  11. 詢問 "2 1 2". 字串: "CABDA". 子串 $t[1..2]$ = "CA", 答案: 1. 字串保持唔變。
  12. 詢問 "3 4 5". 字串: "CABDA". 子串 $t[4..5]$ = "DA", 答案: 1. 變化之後:"DA" $\rightarrow$ "AD"。字串變成 "CABAD"。
  13. 詢問 "2 3 5". 字串: "CABAD". 子串 $t[3..5]$ = "BAD", 答案: 1. 字串保持唔變。
  14. 詢問 "1 2 B". 原本係 "CABAD",而家係 "CBBAD"。
  15. 詢問 "2 1 5". 字串: "CBBAD". 子串 "CBBAD", 答案: 9. 字串保持唔變。
  16. 詢問 "3 1 1". 字串: "CBBAD". 子串 $t[1..1]$ = "C", 答案: 0. 對長度為 1 嘅子串排序唔會改變任何嘢,字串維持係 "CBBAD"。
  17. 詢問 "2 1 1". 字串: "CBBAD". 子串 $t[1..1]$ = "C", 答案: 0. 字串保持唔變。
  18. 詢問 "1 4 D". 原本係 "CBBAD",而家係 "CBBDD"。
  19. 詢問 "2 1 5". 字串: "CBBDD". 子串 $t[1..5]$ = "CBBDD", 答案: 3. 字串保持唔變。
  20. 詢問 "3 1 5". 字串: "CBBDD". 子串 $t[1..5]$ = "CBBDD", 答案: 3. 變化之後:"CBBDD" $\rightarrow$ "BBCDD"。最終字串係 "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.