#19584: 線段樹*2


ntnuapcs1936 (ntnuapcs1936)

學校 : 國立臺灣師範大學附屬高級中學
編號 : 94093
來源 : [220.137.238.58]
最後登入時間 :
2021-11-07 10:26:02
d801. SCOI2006 2.动态最值(minmax) -- SCOI2006第二题 | From: [36.226.121.153] | 發表日期 : 2019-10-11 18:59

若只是求區間極值和單點修改用一個線段樹就夠了

遇到刪除時?

基本想法是不移動任何元素

用一個線段樹維護極值,單點刪除只要將min=inf, max=-inf,就不會被之後的求值過程考慮到了

至於刪除後合併陣列的部分,要是能知道詢問點在原陣列中的位置就可以輕鬆求值

於是這裡開了一條全是1的陣列,表示元素的存在與否

這樣只要找到一個點的前綴和(線段樹2)恰等於詢問點,該點即為原本的位置

搜尋的部分就只是變形的dfs(注意搜尋時找的點可能已經被刪除)

 

 
ZeroJudge Forum