TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

90.0% (27/30)

Submission's AC Ratio

19.0% (100/525)

Tags

Description

這題的題目是要你插入或重新插入一些數字,並且確定數字的大小。
以下是題目敘述,如果你很趕時間最好可以直接跳過去看輸入說明。


你看過coding days嗎?那是一個真實、感人、卻又反映出人性黑暗的故事。

就算你沒聽過,你也知道甚麼是「編譯器」,那個人,對,就是誠哥,那個曾經試圖自己改寫一個不會編譯錯誤的編譯器,這就是他的故事。

誠哥在找對象實驗編譯器時在電車上看到了int,想要將數值塞入int,string是他的好友,就跟他模擬插數字,int不久就跟編譯器連結,但誠哥漸漸發現了string的美好,於是也想要將數值塞入string。

int不願讓誠哥的編譯器捨棄了自己這個唯一的插入選擇,而string成為了被塞入的容器感到喜悅,然而此時誠哥因為摸透了int的底,就開始到處亂塞數值,面對一整排的資料結構,double float都成功被誠哥的編譯器塞入了,但在嘗試塞入char時正好被int撞見,int受到了重創便黑化了。

string仍不知誠哥在自己背後偷塞數字,int告訴string事實,string為了證明自己是誠哥的最愛,到處宣揚自己裡面已經有了被編他的譯器插入的數值,在重重的壓力下,string也壞掉了。

在一個晚上,string爆走了,拿刀捅爛了誠哥和他的編譯器,int發現後把他的編譯器裝入了袋子裡,利用編譯器傳了訊息給string,要求他到頂樓,int認為string說謊,因為string不可能被塞入數值,但string死不承認,int指著裝著誠哥編譯器的袋子,說如果不信的話我們可以問誠哥啊,string往袋子裡一探,立刻崩潰跪在地上,int把握住了這個空檔,先是一個去去武器走,再接著一個劈斬,string腹部破裂,int嘴角揚起露出一抹微笑,啊~果然是騙人的,string裡面根本沒有數字。

隔天int帶著被砍爛的string和誠哥的編譯器乘上了一艘油輪,航向了遠方。

你,瑞男,在知道故事後,非常的驚訝,原來誠哥根本沒有在string裡插入數字,我們可以合理的懷疑誠哥根本就沒有插入任何的數字,也許就算紀錄說有也不用理他,我們相信如果紀錄裡出現了插入的動作,我們也只要輸出一行7122,但是無論如何,你在一次營隊中透露了想要寫編譯器的意圖,被同一個營隊的友人制止了並告訴你這個故事。雖然你放棄了寫編譯器的 幻想 想法,但是你還是想要分析一下誠哥的編譯器對那一群資料結構的一些操作和結果。顯然有些動作是不存在的,現在你必須寫個程式好好檢查他。而且你又發現,資料結構會變得那麼不穩定又一部份是因為數值改變的原因,為了好好分析一下以防以後CE,你想要看看某個區間第K小的數字是多少。


以上是題目敘述,相信你已經仔細的看完了。

Input Format

第一行有一個整數T,代表「好船」上有幾筆編譯器資料。

以下是你在「好船」上撿到的編譯器資料。
第1行兩個整數N Q,代表總共有N個資料結構和有Q個操作紀錄。
第2行有N個整數Ai,代表第i個資料結構的數值。
接下來有Q行,
如果是 1 l r k,你想紀錄[l,r]的第k小的數字。
如果是 2 c v,你想要把位置c的值改成v,好讓你可以觀察她們的情緒變化。
如果是 3 x v,也許代表誠哥的紀錄說他想在x這個位置插入一個新的資料結構,讓他數值是v吧。(關於這項操作,詳細的內容請觀察題目敘述)

因為誠哥的long long和編譯器吵架了,紀錄裡不會出現大於231 -1的數字。
對於30%的測試資料,Q≤200。
對於20%的測試資料,不會有更新和插入。
對於所有的測資,N≤50000,Q≤10000,1≤l≤r≤N,1≤c≤N,1≤k≤r-l+1。

Output Format

請你告訴大家,對於第1種操作查詢的結果, 裡面到底有沒有人

Sample Input

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

Sample Output

6
5
2
0

Hints

你真的看清楚題目敘述了嗎?你真的真的看清楚了嗎?你真的真的真的看清楚了嗎?
好吧,如果你還是看不懂的話,你可以去這裡看。

Problem Source

果茶

注:誠哥的編譯器紀錄檔案還真大,傳了2個多小時才傳完呢...。

Subtasks

For Testdata: 0 ~ 2, Score: 30
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 9, Score: 50
No. Time Limit (ms) Memory Limit (KiB)
0 3000 131072
1 3000 131072
2 3000 131072
3 5000 131072
4 3000 131072
5 3000 131072
6 3000 131072
7 3000 131072
8 3000 131072
9 3000 131072