1. 首頁 > 生活百科 > >

P7476 苦澀 題解

生活百科P7476 苦澀 題解

Link
一道很好的復雜度均攤題目 。
只需要考慮刪除操作時的時間復雜度 。保證復雜度的重點之一是精確定位到所有包含最大值的區間 ， 即不去碰多余的區間 。每次刪除操作會刪除若干個整個區間，以及至多兩個區間被刪一半 。
由于一共最多插入了 \(O(m\log n)\) 個區間，所以前一半的復雜度是對的 。
對于后一半，直接暴力將區間切半向下遞歸，于是兩個兒子要么一個留下一個遞歸，要么一個刪掉一個遞歸，遞歸層數至多 \(O(\log n)\)，于是這一步復雜度也至多 \(O(m\log n)\) 。
總共復雜度就倆 \(\log\)（注意其中一個是 set 的，線段樹只有一個 \(\log\)?。?
【P7476 苦澀 題解】

    推薦閱讀