56 . abc 分組問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

45.8% (11/24)

Tags

ioicamp ioicamp-2024

Description

長頸鹿大學的運動會要開始了！為了炒熱氣氛，有 N 個人正在玩一個遊戲。他們排成一列，從左到右編號依序為 1,2,…,N，且每個人會拿著一個字母牌子，牌子的字母只會是 abc 其中之一。

接下來他們會進行 Q 次活動，每次活動可能會是以下兩種之一：

  • 大風吹：給定 li,ri，他們會將編號介於 li 到 ri 之間的人更新手上的牌子。更新方式為：原本手上拿 a 的人變成拿 b、手上拿 b 的人變成拿 c、手上拿 c 的人變成拿 a，請特別注意三種操作是同時進行的。
  • 分組：給定 li,ri，他們會將編號介於 li 到 ri 之間的人分組。其中每個人只能被分到最多一組，同時每一組的成員編號必須要連續，且每一組必須要包含至少一個 a、一個 b 與一個 c。特別注意的是一個人沒有被分配到任何組是被允許的。

身為長頸鹿大學的校長，球球已經得知了這 Q 次活動的內容，他想要知道對於每一次的分組活動，他們最多可以分成幾組。身為球球的助理，請幫助他求出答案。

Input Format

輸入第一行有兩個整數 N,Q，分別代表人與活動的數量。

輸入第二行有一個長度為 N 的字串 S，其中 Si 代表編號為 i 的人一開始手上拿著的字母。

接下來 Q 行，第 i 行有三個數字 opi,li,ri，代表第 i 次活動的資訊，若 opi=1 則代表這次活動為大風吹，若 opi=2 則代表這次活動為分組。li,ri 的定義則與題目敘述相同。

  • 1≤N,Q≤2×105
  • |S|=N
  • Si∈{a,b,c}
  • opi∈{1,2}
  • 1≤li≤ri≤N

Output Format

對於每一個分組活動，輸出一行，該行有一個整數代表最多的分組數量。

Sample Input 1

9 10
abcabcabc
2 1 9
2 3 8
1 2 5
2 1 9
1 6 8
2 3 9
1 1 9
1 3 6
2 2 9
2 5 6

Sample Output 1

3
2
2
2
1
0

Sample Input 2

20 20
aabacbcbcacacababaac
2 10 19
2 7 20
2 5 18
2 3 14
2 2 16
2 3 16
2 4 15
2 11 20
2 10 20
2 9 18
2 2 14
2 11 20
2 1 13
2 11 20
2 10 20
2 2 15
2 5 20
2 9 18
2 11 20
2 4 20

Sample Output 2

1
3
2
2
3
3
3
2
2
1
2
2
2
2
2
3
3
1
2
4

Sample Input 3

20 20
cccbabbaacccbcacbcba
1 2 16
2 5 11
1 8 16
2 9 16
1 12 18
2 6 16
1 5 12
2 4 9
1 15 19
2 11 19
1 6 16
2 12 20
1 8 16
2 6 15
1 8 15
2 7 17
1 5 11
2 11 14
1 5 11
2 12 19

Sample Output 3

1
1
1
0
3
3
1
3
1
2

Hints

以下為範例測試資料一每個活動的解釋：

  1. 將 abcabcabc 分組，最多可以分成 3 組。
  2. 將 cabcab 分組，最多可以分成 2 組。
  3. 大風吹後，S=acabccabc。
  4. 將 acabccabc 分組，最多可以分成 2 組。
  5. 大風吹後，S=acabcabcc。
  6. 將 abcabcc 分組，最多可以分成 2 組。
  7. 大風吹後，S=babcabcaa。
  8. 大風吹後，S=bacabccaa。
  9. 將 acabccaa 分組，最多可以分成 1 組。
  10. 將 bc 分組，最多可以分成 0 組。

Problem Source

IOICamp 2024 Day6 pI

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~22 opi=2 50
3 3~52 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1048576 65536 1
1 3000 1048576 65536 1
2 3000 1048576 65536 1
3 3000 1048576 65536 2 3
4 3000 1048576 65536 2 3
5 3000 1048576 65536 2 3
6 3000 1048576 65536 2 3
7 3000 1048576 65536 2 3
8 3000 1048576 65536 2 3
9 3000 1048576 65536 2 3
10 3000 1048576 65536 2 3
11 3000 1048576 65536 2 3
12 3000 1048576 65536 2 3
13 3000 1048576 65536 2 3
14 3000 1048576 65536 2 3
15 3000 1048576 65536 2 3
16 3000 1048576 65536 2 3
17 3000 1048576 65536 2 3
18 3000 1048576 65536 2 3
19 3000 1048576 65536 2 3
20 3000 1048576 65536 2 3
21 3000 1048576 65536 2 3
22 3000 1048576 65536 2 3
23 3000 1048576 65536 3
24 3000 1048576 65536 3
25 3000 1048576 65536 3
26 3000 1048576 65536 3
27 3000 1048576 65536 3
28 3000 1048576 65536 3
29 3000 1048576 65536 3
30 3000 1048576 65536 3
31 3000 1048576 65536 3
32 3000 1048576 65536 3
33 3000 1048576 65536 3
34 3000 1048576 65536 3
35 3000 1048576 65536 3
36 3000 1048576 65536 3
37 3000 1048576 65536 3
38 3000 1048576 65536 3
39 3000 1048576 65536 3
40 3000 1048576 65536 3
41 3000 1048576 65536 3
42 3000 1048576 65536 3
43 3000 1048576 65536 3
44 3000 1048576 65536 3
45 3000 1048576 65536 3
46 3000 1048576 65536 3
47 3000 1048576 65536 3
48 3000 1048576 65536 3
49 3000 1048576 65536 3
50 3000 1048576 65536 3
51 3000 1048576 65536 3
52 3000 1048576 65536 3
Submit
Back to Top