hdu 2795 Billboard 线段树

#include<bits/stdc++.h>
using namespace std;

const int N= 200000+5;
int a[N],ans;

struct Tree
{
    int left,right;
    int sum;
}tree[4*N+10];

void build(int id,int l,int r)
{
    tree[id].left=l;
    tree[id].right=r;
    if (l==r)
        tree[id].sum=a[l];
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        tree[id].sum=max(tree[id*2].sum,tree[id*2+1].sum);
    }
}


void update(int id,int pos,int val)
{
    if (tree[id].left==tree[id].right)
        tree[id].sum=tree[id].sum-val;
    else
    {
        int mid=(tree[id].left+tree[id].right)/2;
        if (pos<=mid) update(id*2,pos,val);
        else update(id*2+1,pos,val);
        tree[id].sum=max(tree[id*2].sum,tree[id*2+1].sum);
    }
}

//查询范围内的和
int query(int id,int val)
{
    int ret;
    if (tree[id].left==tree[id].right)
    {
       tree[id].sum=tree[id].sum-val;
        return tree[id].left;
    }
    else
    {
        if(tree[id*2].sum>=val) ret=query(id*2,val);
        else ret=query(id*2+1,val);
    }
    tree[id].sum=max(tree[id*2].sum,tree[id*2+1].sum);
    return ret;
}

int main()
{
    int i,h,w,n,t;
    while(~scanf("%d%d%d",&h,&w,&n))
    {
        if(h>n) h=n;
        for(i=1;i<=h;i++)
            a[i]=w;
        build(1,1,h);
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);
            if(tree[1].sum<t) printf("-1
");
            else
            {
                ans=query(1,t);
                printf("%d
",ans);
                //printf(" %d
",tree[ans].sum);
            }
        }
    }
    return 0;
}