a632. D. Benson 的美術課 - 旦旦解題農場

內容

平常十分討厭美術課的 Benson 今天也不例外呢(X)。今天老師特別好，沒有要畫甚麼特色自畫像，也沒有甚麼煩死人的刀刻，只要全班來數顏色就好了，Benson 發現，啊，又是一個補眠的好機會，於是就跟老師說要回教室拿東 (ㄓㄣˇ) 西 (ㄊㄡˊ)，正要熟睡的時候老師突然說：「避免大家消極參與，最快算完的同學可以獲得一杯飲料」。Benson 想了想，不拿白不拿，喝免費的最開心啊 (O)，所以就聽了聽老師的遊戲。

老師：「我會先給每個同學一條彩帶，然後每次會有兩個動作的其中一種，我會先說動作編號。當動作編號為 $0$ 時，我會給兩個數字 $x,v$ 請將彩帶上 $x$ 位置上的顏色改成 $v$；當動作編號為 $1$ 時，我會給兩個數字 $l,r$，你要告訴我彩帶的 $[l,r]$ 之間有多少不同的數字。」Benson 聽了之後覺得自己超電可以花 5 分鐘寫好一份程式後就可以睡覺，很開心。因為 Benson 同時也是 AI 高手，所以對於聲音辨識、資料轉換早就寫過了，甚至有模板，完全不用擔心，只要完成這堂課老師所求的部分就好了。現在來看看是 Benson 寫得比較快還是你寫的比較快！

輸入說明

第一行有兩個數 $N,Q$ 表示陣列彩帶長度、動作次數。

第二行會有 $N$ 個數代表彩帶的顏色，

接下來 $Q$ 行，

每次會先讀入 $op$ 代表動作，

$op=1$，讀入 $l,r(1\le l,r\le N)$，詢問 $[l,r]$。
$op=0$，讀入 $x,v$，將 $a_x$ 改為 $v$。

輸出說明

對每個 $op=1$ 輸出題敘所求。

範例輸入

6 7
1 1 1 1 1 1
1 1 6
0 2 2
1 2 3
0 6 4
0 4 8
0 5 8
1 1 6

範例輸出

1
2
4

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

提示：

對於 $20\%$ 的測資，有 $1\le N,Q\le100$。
對於 $100\%$ 的測資，有 $\forall op\in\{0,1\},1\le N,Q\le3\times10^4,1\le a_i\le10^6(1\le i\le N)$。

標籤:

出處:

DDJ Regular Contest Round#6 [管理者：

fdhs109_GT (9th 進階助教)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」