1169 . 氣球博覽會
TopCoder
Description
在氣球博覽會裡面，有N顆氣球排成一列，由0編號到N-1。所有氣球博覽會中可以提供的氣球顏色可以用一個C位元的無號整數型態（代表的數範圍是$[0,2^ C)$）表達。（例如24位元即是常用的RGB表示法。）
你身為氣球博覽會的導覽員，（枯燥的）工作就是要在指定的時間把這排氣球中某個編號的氣球換成指定的顏色。
當然，既然叫做博覽會，就會有一些人在任意的時刻來參觀，而且每個人都想要參觀某些顆相鄰的氣球（稱為「參觀範圍」）。很不幸地，來參觀的每個人都恰很討厭一種顏色。但是因為這排氣球實在是太多了，所以你可以把每個人帶到一個「參觀範圍」內的位置參觀，使得那個位置附近都沒有他討厭的那個顏色。所以你需要知道在某參觀範圍內，最長連續不含某顏色的氣球區間有多長（以那個區間有幾顆氣球計算）。
由於氣球和來參觀的人實在是太多了，你需要寫一個程式來幫你回答問題。
Input Format
第一行有三個正整數$N,Q,C$，分別代表氣球個數、操作次數與表達顏色是用幾位元的整數型態。
第二行有$N$個非負整數$A_i$，依序代表每個氣球的顏色。
接下來有$Q$行，每行代表一個操作。
如果是0 P K，代表把編號為P的氣球換成顏色K。
如果是1 X Y K，代表詢問$[X,Y)$區間最長不包含顏色K氣球的區間長度。
對於所有測資，$N, Q\leq 2\times 10^ 5; C \leq 24; A_i, K<2^ C$。
保證所有操作都是合法的，並且不會詢問空區間。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~2) | $N, Q\leq 3000$ | 9 |
| 2 (3~5) | 沒有修改操作 | 16 |
| 3 (6~8) | $C\leq 4$ | 23 |
| 4 (9~11) | $N, Q\leq 4\times 10^ 4$ | 17 |
| 5 (0~17) | 無限制 | 35 |
Output Format
對於每個詢問，輸出一行非負整數，代表最長不包含該顏色的區間長度。
Sample Input 1
5 5 4
0 1 2 1 2
1 0 5 2
0 1 3
1 2 4 3
0 3 3
1 1 5 3
0 1 2 1 2
1 0 5 2
0 1 3
1 2 4 3
0 3 3
1 1 5 3
Sample Output 1
2
2
1
2
1
Hints
Problem Source
Problem set / Description by Yihda Yol
建國中學105學年度校內第三次模擬賽pD
題目取自2015 TOI第一階段選訓第一次模擬考pC
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~2 | 9 |
| 2 | 3~5 | 16 |
| 3 | 6~8 | 23 |
| 4 | 9~11 | 17 |
| 5 | 0~17 | 35 |