Universal Cup Judging System

Universal Cup

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

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.