斑的家

E. George and Cards

這題一看到題目，就想到greedy+資料結構去加速。

核心思想是找到一段在array 連續的數字，使得要刪除的數字是裡面最小的。

首先找到目前最小要刪除的數字 m

令 m 在 array 的index 是 pos[m] 

l 為此段最左, r為此段最右。

那麼就找到w = r - l + 1，但是在 [l,r] 中有些數字已經刪除了，利用 BIT 去記錄，所

以真正的 w = r - l + 1 - ( read(r) - read(l-1)) ;

這樣的做法有二個重要的地方。

1. 找到目前最小要刪除的數字。

 記錄哪些要刪掉，然後用 sort

2. 找 l ,r 。

我利用segment tree 做 RMQ + binary search

對於l, 從segment tree 的觀點，我已經知道我要找的qr = pos[m] , 但是ql 並不清楚，這時用 binary search 去找。

對於r , 同上。只是知道ql =pos[m], qr 未知。

這是size 是1000000，我的做法 O(n) = n (logn)^2 。就 TLE 了。

後來看了其他人的做法還蠻簡單的，sort 原本的 array ，但要記錄原本的 index ( idx array )。開一個 set 叫 s 。

從i =1 ... n , i 表示array 的element 數值

如果 i 是要刪除的數字那麼

l = *(--s.upper_bound(idx[i]));   (A)

r = *(s.upper_bound(idx[i]));    (B)

l++, r--;

w = r - l + 1 - (read(r) - read(l-1));

update(idx[i],1);

% update 和 read 函式給 BIT 用的。

若非刪除的數字則

  s.insert(idx[i]);

原理在於，數字是從小到大考慮，對於一個要刪除的數字，從s.upper_bound (A),(B)得到的l,r一定是某個比

現在要刪除的數字還要小的數字，因此若要延伸l,r ，最遠也只能延伸到此。