227 . 如果我有一座新冰箱
TopCoder
Tags
Description
身為一個資深ㄌㄌ控，bb 買了一座有 \(N\) 個格子的新冰箱來冷藏他的ㄌㄌ收藏，格子的編號依序由左往右是 \(1\sim N\)。
但是 bb 收藏的ㄌㄌ都很傲嬌，她們討厭和其他ㄌㄌ分享 bb ，因此希望離其他ㄌㄌ越遠越好。每當一個ㄌㄌ要進入冰箱，她會去找一個位置使得離他最近的ㄌㄌ距離盡量遠，如果有很多位置離最近的ㄌㄌ距離都相同，她會選擇其中最左邊的。而且因為這些ㄌㄌ都很傲嬌，她們也不希望離冰箱的邊緣太近，他們對冰箱邊緣的厭惡度等同於你在第 \(0\) 格和第 \(N+1\) 格都擺上一個ㄌㄌ。
作為專業的ㄌㄌ收藏家，bb 把每個ㄌㄌ都設置了一個屬性（屬性是一個 \(1\sim 10^ 9\) 的整數）。但 bb 是個喜新厭舊的人，他有時候會把某個屬性的ㄌㄌ全部趕出去，以空出空間容納新的ㄌㄌ。
bb 的好友小 y 和小 p 想要知道在 2020 年，bb 收（ㄖㄢˇ）藏（ㄓˇ）了多少蘿莉，於是就偷走了 bb 的記帳手冊。上面詳列了 bb 收養了哪些ㄌㄌ以及他趕走了哪些ㄌㄌ，為了向警察杯杯完整還原事發經過，小 y 和小 p 打算在記錄裡補上每一個ㄌㄌ被收養之後住進冰箱的哪個格子。
在認真整理之後，小 y 和小 p 發現 bb 的ㄌㄌ數量大到連他自己都搞不清楚，有時候他想要趕走的ㄌㄌ屬性根本不存在（這種時候當然什麼都沒趕走），有時候他把ㄌㄌ帶回冰箱的時候ㄌㄌ冰箱是滿的，這樣ㄌㄌ就會自己落跑。小 y 和小 p 已經處理到頭腦過熱想要放進冰箱冷卻一下了，請你寫一隻程式幫他們整理這些紀錄吧！
Input Format
第一行有兩個正整數 $N,Q$，代表 bb 的新冰箱有 $N$ 格。
第二行有 $N$ 個整數 $a_i$，依序代表在 2020 年開始之前，住在第 $i$ 個格子的ㄌㄌ的屬性，如果 $a_i=0$ 代表第 $i$ 個格子沒有住ㄌㄌ。
接下來的 $Q$ 行，每行有兩個正整數 $t_i,k_i$，代表第 $i$ 筆紀錄的內容。如果 $t_i=0$，表示 bb 把一隻屬性是 $k_i$ 的ㄌㄌ加入冰箱裡。如果 $t_i=1$，表示 bb 把所有屬性是 $k_i$ 的ㄌㄌ都趕出冰箱了。
- $1\leq N,Q\leq 2\times 10^ 5$
- $0\leq a_i \leq10^ 9$
- $t_i \in\lbrace 0,1\rbrace$
- $1\leq k_i \leq10^ 9$
Output Format
對於每一筆 $t_i=0$ 的紀錄輸出一行，包含一個正整數 $pos$ ，代表這隻ㄌㄌ入住了冰箱的第 $pos$ 格。
如果這個時候冰箱根本是滿的，請輸出 -1 並不要更動冰箱的內容。
Sample Input 1
0 10 3 0 2
1 10
0 3
0 9
1 3
1 2
0 8
Sample Output 1
2
4
Hints
Problem Source
IOICamp 2021 Day5 pB
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~29 | 無額外限制 | 100 |