HDU 2795 Billboard【点修改】

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define L l,m,rt<<1
#define R m+1,r,rt<<1|1  //u*2+1

const int N = 200000 + 10;
int h,w,n;
int a[N << 2];

void build(int l,int r,int rt)                                                       //建立线段树的规则为，最后叶子的序号与层数的序号相对应，比如第一片叶子表示第一层……  每一个节点的区间范围表示对应的层数范围
{                                                                                         //若a[rt]表示的是叶子，则a[rt]的值为对应层剩余的长度
    a[rt] = w;   //因为开始每一层都是剩余w的长度，所以每一个节点都初始化为w                   //若a[rt]表示的是节点，则a[rt]的值表示该节点对应区间（层数）的剩余长度的最大值（在下面query()函数的过程中有体现）
    if (l == r)
        return;
    int m = (l + r) >> 1;
    build(L);
    build(R);
}

int query(int x,int l,int rt)
{
    if (l == r)   
    {
        a[rt] -= x;     //由于题目说了在每一层，纸条是优先放在最左边（优先放最右边也一样），所以，对于这种连续的放置，就可以直接转化为数值的加减就可以，如果题目规定了纸条放置的不同规则，那么纸条的放置则可能需要模拟了
        return l;
    }
    int m = (l + r) >> 1;
    int res = (a[rt << 1] >= x) ? query(x,L) : query(x,R);
    a[rt] = max(a[rt << 1],a[rt << 1 | 1]);           //递归到叶子后，由于该叶子对应层的剩余长度已经改变，所以线段树对应路径上的节点的值也应该随之改变，同时可以根据这里可以看出，该线段树每个节点存储的值为该节点对应区间（对应层数）中剩余长度的最大值
    return res;
}

int main()
{
    while (~scanf("%d%d%d",&h,&w,&n))
    {
        if (h>n)
            h = n;
        build(1,h,1);
        while (n--)
        {
            int x;
            scanf("%d",&x);
            if (a[1]<x)         //a[i]存放的是第i层所能存放的最长长度，因此a[1]表示所有层中剩余长度最长的长度，因为此线段树的节点与叶子的关系为，a[rt] = max(a[rt << 1],a[rt << 1 | 1]);
                printf("-1n");
            else
                printf("%dn",query(x,1,1));
        }
    }
    return 0;
}