#19584: 線段樹*2


ntnuapcs1936 (ntnuapcs1936)

學校 : 國立臺灣師範大學附屬高級中學
編號 : 94093
來源 : [220.137.238.58]
最後登入時間 :
2021-11-07 10:26:02

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

遇到刪除時?

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

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

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

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

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

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