Rejudge 公告 718, 552 已新增測資並 rejudge
IOICamp 2024 題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
停機公告 今（2025/01/15）15:00～18:00 本站將進行系統維護，期間將無法評分提交的程式碼。
IOICamp 2024 題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
停機公告 今（2025/01/15）15:00～18:00 本站將進行系統維護，期間將無法評分提交的程式碼。
56 . abc 分組問題
TopCoder
Tags
Description
長頸鹿大學的運動會要開始了！為了炒熱氣氛，有 $N$ 個人正在玩一個遊戲。他們排成一列，從左到右編號依序為 $1, 2, \ldots, N$，且每個人會拿著一個字母牌子，牌子的字母只會是 $\texttt{abc}$ 其中之一。
接下來他們會進行 $Q$ 次活動，每次活動可能會是以下兩種之一：
- 大風吹：給定 $l_i, r_i$，他們會將編號介於 $l_i$ 到 $r_i$ 之間的人更新手上的牌子。更新方式為：原本手上拿 $\texttt{a}$ 的人變成拿 $\texttt{b}$、手上拿 $\texttt{b}$ 的人變成拿 $\texttt{c}$、手上拿 $\texttt{c}$ 的人變成拿 $\texttt{a}$，請特別注意三種操作是同時進行的。
- 分組：給定 $l_i, r_i$，他們會將編號介於 $l_i$ 到 $r_i$ 之間的人分組。其中每個人只能被分到最多一組，同時每一組的成員編號必須要連續，且每一組必須要包含至少一個 $\texttt{a}$、一個 $\texttt{b}$ 與一個 $\texttt{c}$。特別注意的是一個人沒有被分配到任何組是被允許的。
身為長頸鹿大學的校長，球球已經得知了這 $Q$ 次活動的內容，他想要知道對於每一次的分組活動，他們最多可以分成幾組。身為球球的助理，請幫助他求出答案。
Input Format
輸入第一行有兩個整數 $N, Q$，分別代表人與活動的數量。
輸入第二行有一個長度為 $N$ 的字串 $S$，其中 $S_i$ 代表編號為 $i$ 的人一開始手上拿著的字母。
接下來 $Q$ 行，第 $i$ 行有三個數字 $op_i, l_i, r_i$，代表第 $i$ 次活動的資訊，若 $op_i = 1$ 則代表這次活動為大風吹，若 $op_i = 2$ 則代表這次活動為分組。$l_i, r_i$ 的定義則與題目敘述相同。
- $1 \leq N, Q \leq 2 \times 10^ 5$
- $|S| = N$
- $S_i \in \lbrace\texttt{a}, \texttt{b}, \texttt{c}\rbrace$
- $op_i \in \lbrace1, 2\rbrace$
- $1 \leq l_i \leq r_i \leq 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
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
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
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
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
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
1
1
0
3
3
1
3
1
2
Hints
以下為範例測試資料一每個活動的解釋：
- 將 $\texttt{abcabcabc}$ 分組，最多可以分成 $3$ 組。
- 將 $\texttt{cabcab}$ 分組，最多可以分成 $2$ 組。
- 大風吹後，$S = \texttt{acabccabc}$。
- 將 $\texttt{acabccabc}$ 分組，最多可以分成 $2$ 組。
- 大風吹後，$S = \texttt{acabcabcc}$。
- 將 $\texttt{abcabcc}$ 分組，最多可以分成 $2$ 組。
- 大風吹後，$S = \texttt{babcabcaa}$。
- 大風吹後，$S = \texttt{bacabccaa}$。
- 將 $\texttt{acabccaa}$ 分組，最多可以分成 $1$ 組。
- 將 $\texttt{bc}$ 分組，最多可以分成 $0$ 組。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 3~22 | $op_i = 2$ | 50 |
| 3 | 3~52 | 無額外限制 | 50 |