HDU 2795 Billboard.(線段樹)

HDU 2795 Billboard.(線段樹)

題目連接：http://acm.hdu.edu.cn/showproblem.php?pid=2795

~~~~

開始學習數據結構，從簡單的開始吧，刷題累了就寫解題報告，哈哈，沸騰吧，Segment tree!

~~~~

大致題意：一塊 h*w的廣告牌，藍後就是n塊1*wi大小的廣告，依次貼到廣告牌上，而且總是貼到最左上角，問貼完所有廣告後所占的高度是多少？

#include
#include
#define lson rt<<1,s,mid
#define rson rt<<1|1,mid+1,e
using namespace std;

const int maxn=222222;
int tre[maxn<<2];
int h,w,n;

void pushup(int rt)
{
    tre[rt]=max(tre[rt<<1],tre[rt<<1|1]);
}

void build(int rt,int s,int e)
{
    tre[rt]=w;
    if(s==e)
        return ;
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
}

int query(int rt,int s,int e,int x)
{
    if(s==e)
    {
        tre[rt]-=x;
        return s;
    }
    int mid=(s+e)>>1;
    int ans=(tre[rt<<1]>=x)?query(lson,x):query(rson,x);
    pushup(rt);     //直接把更新操作寫到query函數裡。
    return ans;
}

int main()
{
    while(scanf("%d%d%d",&h,&w,&n)==3)
    {
        if(h>n) h=n;    //h>n的話，多余的就空間就浪費掉了，而且貌似會RE
        build(1,1,h);
        while(n--)
        {
            int q;
            scanf("%d",&q);
            if(tre[1]