我們來(lái)看一個(gè)題，是上周日的力扣周賽T4。本身這題很簡(jiǎn)單，直接排序+貪心就能解決，復(fù)雜度為。

但如果數(shù)據(jù)范圍從2000擴(kuò)大到, 我們?cè)撛鯓觾?yōu)化呢？

首先，貪心和排序必不可少，這使得每個(gè)任務(wù)的工作時(shí)間重疊得最多。我們需要優(yōu)化第二重循環(huán)。首先我們要快速求出[start, end]內(nèi)已經(jīng)被填滿了幾個(gè)位置，如果已填滿位置數(shù)量cur < du, 我們還需從右往左填du - cur個(gè)空位，那么就要快速找到一個(gè)位置, 使得區(qū)間內(nèi)未被填滿的位置數(shù)量與cur之和恰好等于du，然后將全部填滿。

考慮懶標(biāo)記線段樹(shù)，支持區(qū)間查詢、區(qū)間修改。關(guān)鍵是如何快速找到idx. 由于線段樹(shù)維護(hù)一個(gè)前綴和，是遞增的，因此可以用二分解決?？梢栽谕獠慷?，利用query函數(shù)，這樣復(fù)雜度為。也可以在線段樹(shù)上直接二分，復(fù)雜度為

具體來(lái)說(shuō)，我們定義一個(gè)search函數(shù)作為二分查找函數(shù)，其參數(shù)為u, R, target, u表示當(dāng)前線段樹(shù)結(jié)點(diǎn)，R表示固定的右端點(diǎn)(我們是固定住右端點(diǎn)往二分找滿足target的最靠右的左端點(diǎn)), target: 需要填的位置個(gè)數(shù).?

如果線段樹(shù)節(jié)點(diǎn) , 則檢查tr[u]所表示的區(qū)間內(nèi)是否有target個(gè)空位置，若, 返回 -tr[u].cnt, 表示這tr[u].cnt個(gè)空位我已經(jīng)填了，后面的操作無(wú)需再填。

然后就是常規(guī)操作，不過(guò)要注意，由于要往右貪心，我們先遞歸右子樹(shù)，不夠的話再遞歸左子樹(shù)。完整代碼如下：