好一陣子沒有寫到RMQ了
連結：TOJ266 水桶和水球
題目：
有N個水桶Q次操作，操作分兩種
- 0, p, v：在編號p的水桶裡放置價值為v的水球
- 1, l, r：從l到r中拿出價值最大的水球(拿出就丟棄)，若有價值相同的多顆，拿編號最大的
做法：
一個水桶將能放置多顆水球，而須取出價值最大的，所以用個最大堆維護
線段樹的節點需要維護該區間的最大水球及其編號，因為拿完要刪除
這裡我寫了三個function: add(), del(), query()，其中add和del會一併更新
編號是0~N-1，故初始化為-1
code:
沒有留言:
張貼留言