TopCoder

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

User's AC Ratio

88.2% (60/68)

Submission's AC Ratio

21.1% (219/1036)

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$ 個整數 $A_i$,代表第i個資料結構的數值。
接下來有 $Q$ 行,
如果是 1 l r k,你想紀錄 $[l, r]$ 的第 $k$ 小的數字。
如果是 2 c v,你想要把位置 $c$ 的值改成 $v$,好讓你可以觀察她們的情緒變化。
如果是 3 x v,也許代表誠哥的紀錄說他想在 $x$ 這個位置插入一個新的資料結構,讓他數值是 $v$ 吧。(關於這項操作,詳細的內容請觀察題目敘述)

因為誠哥的 long long 和編譯器吵架了,紀錄裡不會出現大於 $2 ^ {31} -1$ 的數字。
對於所有的測資:

  • $N \le 50000$
  • $Q \le 10000$
  • $1 \le l \le r \le N$
  • $1 \le c \le N$
  • $1 \le k \le 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個多小時才傳完呢...。

2021.03.19 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Constraints Score
1 0~2 Q≤200 30
2 3 不會有更新和插入 20
3 4~9 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 131072 262144 1
1 3000 131072 262144 1
2 3000 131072 262144 1
3 5000 131072 262144 2
4 3000 131072 262144 3
5 3000 131072 262144 3
6 3000 131072 262144 3
7 3000 131072 262144 3
8 3000 131072 262144 3
9 3000 131072 262144 3