Universal Cup Judging System

Universal Cup

حد الوقت: 5.5 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

클레오파트라는 문자열을 좋아합니다. 길이 $n$인 문자열 $s$(문자 $s[1], \dots, s[n]$으로 구성됨)가 주어지면, 그녀는 즉시 이를 정렬하기 시작합니다. 정렬 과정에서 그녀는 $s[i] \leftrightarrow s[i + 1]$ 형태의 교환 연산을 여러 번 수행하는데, 여기서 $i \in \{1, 2, \dots, n - 1\}$입니다. 마지막에 그녀는 정렬된 문자열을 돌려주며, 수행한 모든 교환에서 $i$의 합과 같은 개수의 금화를 요구합니다 (같은 $i$에 대해 교환이 여러 번 이루어졌다면, 그 $i$는 교환된 횟수만큼 합에 더해집니다). 클레오파트라는 낭비하지 않습니다. 문자열을 정렬하는 모든 방법 중에서 그녀는 정렬 대가로 받는 금화의 개수가 최소가 되는 방법을 선택합니다.

카트린 드 메디시스 또한 문자열을 좋아합니다. 그녀는 길이 $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$의 같은 위치에 다시 끼워 넣습니다.

카트린 드 메디시스는 첫 번째 유형의 쿼리는 스스로 처리할 수 있지만, 두 번째와 세 번째 유형의 쿼리는 너무 복잡해서 클레오파트라에게 맡깁니다. 이 과정의 비용을 책정할 때, 클레오파트라는 문자열 $s$에서의 인덱스($i$부터 $j$까지)가 아니라 부분 문자열의 시작을 기준으로 한 상대적인 인덱스($1$부터 $j - i + 1$까지)를 합산합니다.

카트린 드 메디시스 역시 낭비하지 않으며 자신의 예산을 주의 깊게 관리합니다. 따라서 그녀가 클레오파트라에게 요청하는 각 작업에 대해, 카트린 드 메디시스가 지불해야 할 금화의 개수를 계산하세요.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $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$는 그대로 두고, 부분 문자열 $s[i..j]$를 정렬하는 비용을 구합니다 ($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$입니다.

출력

각 테스트 케이스마다 두 번째와 세 번째 유형의 모든 쿼리에 대한 답, 즉 각 정렬에 대해 클레오파트라가 받게 될 금화의 개수를 각 줄에 하나씩 출력합니다.

예제

예제 입력 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.