HDU-2795: Billboard（单点更新）

线段树

Problem Description

At the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information.

On September 1, the billboard was empty. One by one, the announcements started being put on the billboard.

Each announcement is a stripe of paper of unit height. More specifically, the i-th announcement is a rectangle of size 1 * wi.

When someone puts a new announcement on the billboard, she would always choose the topmost possible position for the announcement. Among all possible topmost positions she would always choose the leftmost one.

If there is no valid location for a new announcement, it is not put on the billboard (that's why some programming contests have no participants from this university).

Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed.

Input

There are multiple cases (no more than 40 cases).

The first line of the input file contains three integer numbers, h, w, and n $(1 <= h,w <= 10^9; 1 <= n <= 200,000)$ - the dimensions of the billboard and the number of announcements.

Each of the next n lines contains an integer number wi $(1 <= wi <= 10^9)$ - the width of i-th announcement.

Output

For each announcement (in the order they are given in the input file) output one number - the number of the row in which this announcement is placed. Rows are numbered from 1 to h, starting with the top row. If an announcement can't be put on the billboard, output "-1" for this announcement.

Sample Input

3 5 5
2
4
3
3
3

Sample Output

1
2
1
3
-1

题意：输入h，w和n，h是板子的宽（高度），w是长，接下来输入n个数，代表n个通告的长度，通告的宽都是1，从左到右，从上向下贴，问每个通告贴在第几排。（要见缝插针啊，如果上面有空位就放在上面），如果不能贴进去，输出-1。
以下是每一次怎么放的样例的简单示意……

分析： 看了不少题解才会写orz
这道题可以用线段树写，叶子节点就是每一层的木板，长度都是w，然后他们的上一层的根节点的长度就是他们中最长的....说得好乱啊我能看懂就行了 因此最外层的那个就是整个木板能放下的最大长度。
还是以样例来说，一共有三排，每排五格，所以初始的时候，所有的节点都是5。然后我们找能放在第几排，先判断这个通告是不是能插进来，就比较s[1].sum和通告长度wi的关系，因为s[1].sum存的是这个木板能容纳的最长的长度。如果能插进来，那么先从左边（也就是上层）开始找，找到满足的叶子节点就可以了。插进去之后减掉这个长度，还要回溯，上一层是下面一层当中的最长长度…

• 完整代码：

#include<stdio.h>
#include<algorithm>
#define maxn 200005
using namespace std;
int ans;
struct node
{
    int l,r,sum;
}s[4*maxn];
void build(int id,int l,int r,int w) //w是每一排的长度
{
    s[id].l=l;
    s[id].r=r;
    s[id].sum=w; //每一排的长都是w
    if(l==r)
        return;
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid,w);
        build(id*2+1,mid+1,r,w);
    }
}
void rep(int id,int w)
{
    if(s[id].l==s[id].r) //叶子节点，就是每一排的木板了
    {
        s[id].sum-=w; //剩下的长度
        ans=s[id].l;
        return;
    }
    else
    {
        if(w<=s[id*2].sum)
            rep(id*2,w);
        else
            rep(id*2+1,w);
        s[id].sum=max(s[id*2].sum,s[id*2+1].sum); //回溯，得到这几层能容纳的最大的长度
    }
}
int main()
{
    int h,w,n,wi;
    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        if(h>n)
            h=n;//最多n个公告，最大高度就是n了
        build(1,1,h,w);
        while(n--)
        {
            ans=-1;
            scanf("%d",&wi);
            if(wi<=s[1].sum) //宽度是小于最大的宽度的(s[1].sum)，就可以插入
                rep(1,wi);
            printf("%d\n",ans);
        }
    }
    return 0;
}