CF436F Banners

首先有n個(gè)物品分別有ai和bi，然后定義價(jià)值為
$$c?w+p?(ai大于p且bi小于c的用戶個(gè)數(shù))$$
然后我們需要求解對(duì)于每一個(gè)c的最大價(jià)值和對(duì)應(yīng)的p

首先我們先枚舉c，然后每次加入一個(gè)點(diǎn)相當(dāng)于是每次給一個(gè)前綴加橫坐標(biāo)，然后詢問最大值。

因?yàn)槊看渭拥拇笮∈且欢ǖ?#xff0c;所以我們可以將其看作是一條直線，然后分塊處理，每次對(duì)于完整的塊就移動(dòng)橫坐標(biāo)，維護(hù)單調(diào)隊(duì)列，將橫坐標(biāo)小的彈掉，然后對(duì)于零散塊直接重建。

所以這道題就是運(yùn)用了分塊來維護(hù)凸包。

總結(jié)

以上是生活随笔為你收集整理的CF436F Banners（分块/凸包/单调队列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。