[IOIcamp2015] 31 - 草莓園保衛戰 II

jd3

遲早會失效的原網址~~~
http://judge.ioicamp.org/problems/31


題意
問區間中是否有
1.重複超過3次的數
2.最大和最小值相差超過51400




解體
區間操作先想到的是一些奇怪的線段數
線段數能輕鬆維護最大最小，重複超過3次卻很棘手

有個東西叫莫隊算法，據說會過可是我寫的複雜度差一個根號 TLE 了 QAQ
(等補充)


接下來傳說是官方解法
經過一番觀察
我們發現對於一個左界 L , 他有最遠右界 R
只要以L為左端，又界<=R則一定是可行的區間

於是想要對於每個左界往右掃看看能到哪
這樣的預處理時間複雜度O(N^2)
輕鬆 TLE


接下來這段理解方式不同是正常的
經過一番精密的觀察得知
對於越右邊的L, 它的R一定越右邊
換句話說就是 R[ i ] <= R[ j ]  (i < j)
而越右端的R, 它的L也一定越右邊
換句話說就是 L[ i ] <= L[ j ]  (i < j)

嗯...這有什麼好處呢?
透過經驗猜想我們需要一個資料結構來維護某些奇怪的資料
然後從左邊慢慢掃過去

然後他一臉蟲樣
看起來就是在爬

於是乎亂做一通
從右邊新加進來的元素 i ,如果不能當 最左邊元素 的R了, 那這個最左邊元素的R就是i-1, 然後左端就可以拔掉一個元素
多維護一個計數用的array, 在加進元素或拔除元素時更新當前有多少個就能判斷加入時是否有超過3個元素

array可以O(1)加入, O(1)查詢單一元素數量
可是沒辦法快速找到最大最小


當然你也可以開個線段數再亂炸一通(不保證常數夠小)
這裡介紹個multiset的東西
log(n)插入, log(n)刪除, log(n)計數
因為內部是個2元搜尋樹之類的東西，是有排序的
查最大最小就是begin() 和 --end()
是O(1)還是O(log(n))我就不清楚了

終於你獲得了一些BUG

然後盲目的殺了半晌
終於AC


如果還想要小加速可以考慮把答案塞進string再輸出XD

以下CODE：
[sojcodepad]d795615d[/sojcodepad]