程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 2795 Billboard（線段樹）

HDU 2795 Billboard（線段樹）

編輯：關於C++

題意：原始序列全為w，找到最左邊的>=a的位置，將該位置的值減去a，答案為該位置，如果找不到符合要求的位置，輸出-1。

該題利用線段樹遞歸特點來求其最左邊的大於等於a的位置。

線段樹遞歸的特點是從祖先結點開始自頂向下遞歸，訪問各個元素的順序一定是從左到右，並且在遞歸之後可以順便維護區間結點的值。

利用這個特點，我們可以直接查詢到>=a的最左邊的位置。該元素變成v - a，然後順便維護改變了的值。所以該題就成了維護區間最大值的線段樹題目。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 200010;
int T,n,w,h,a,m,maxv[maxn*4];
void push_up(int o) {
    maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
}
void build(int l, int r, int o) {
    int m = (l + r) >> 1;
    maxv[o] = w;
    if(l == r) return ;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
    push_up(o);
}
int query(int v, int l, int r, int o) {
    int m = (l + r) >> 1, ans = 0;
    if(l == r) {
        maxv[o] -= v; return l;
    }
    if(maxv[o<<1] >= v) ans = query(v, l, m, o<<1);
    else ans = query(v, m+1, r, o<<1|1);
    push_up(o);
    return ans;
}
int main() {
    while(~scanf("%d%d%d",&h,&w,&n)) {
        if(h > n) h = n;
        build(1, h, 1);
        for(int i=0;i