線段樹 單點更新查詢 區間最大值 hdu 2795 Billboard
題意:
有一塊h*w(1<=h,w<=10^9)的公告牌,需要在上面放n(n<=200000)個1*w[i]的公告,每個公告優先選可以放置的地方中最上的那行,同一行選最左的地方,依次輸出每個公告放置在哪行,如果不能放置,輸出-1。
可以把公告牌看作長為h的線段,構建一個線段樹,每個節點存儲區間的最大值,初始最大值為公告牌的寬度w。如果某區間的最大值大於當前公告的寬度,就可以放在該區間,由於公告優先放在上面,所以選區間的時候也應該先判斷左邊的區間可不可以,當在某個點放上公告後,該點的最大值應減去該公告的寬度。如果整個區間的最大值小於當前公告的寬度,就說明不能放置。
代碼:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include