#19584: 線段樹*2


ntnuapcs1936 (ntnuapcs1936)


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

遇到刪除時?

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

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

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

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

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

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