hdoj2795 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张广告需要贴在上面，每张广告的高度为1，宽度为输入值，贴广告原则：优先靠近顶部，优先靠近左边。问给定宽度的广告贴在第几行（贴不上则为-1）。

一开始我怎么也想不到这道题可以用线段树，看了网上的博客之后才知道这道题也可以用线段树。

由于每张广告的高度固定且都为1，所以就相当于有h个单位长度为1的区间。但h的长度最大可以达到10的9次方，而线段树需要h*4的数组，显然不可能。但是这道题n最多也就200000，因此h最多也只有200000有用，因此可以建成线段树。每行的宽度为维护对象。

参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXV = 200000+10;
using namespace std;
struct node {
    int left,right;
    int maxi;
} e[MAXV * 4];
void init() {
    memset(e,0,sizeof(e));
}
int h,w,n;
void push_up(int p) {
    e[p].maxi = max(e[p*2].maxi, e[p*2+1].maxi);
}
void build(int p,int l,int r) {
    e[p].left = l;
    e[p].right = r;
    if (l == r) {
        e[p].maxi = w;//最开始每个区间都没有贴广告(剩余宽度为w);
    }
    else {
        int mid = (l + r) / 2;//建立线段树;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        push_up(p);
    }
}
int query(int p,int l,int r,int wi) {
    int ans;
    if (e[p].maxi < wi) {//这张广告已经贴不下;
        return -1;
    }
    if (l == r) {//找到了所在的行;
        e[p].maxi = e[p].maxi - wi;//该行的剩余宽度;
        return l;
    }
    int mid = (l + r) / 2;
    ans = query(p*2,l,mid,wi);//寻找是否还有位置(先左后右原则);
    if (ans == -1) {
        ans = query(p*2+1,mid+1,r,wi);
    }
    push_up(p);//维护最大值;
    return ans;
}
int main() {
    while(scanf("%d%d%d", &h, &w, &n) != EOF) {
        init();
        int wi;
        if (h > n) h = n;
        build(1,1,h);
        for (int i = 1;i <= n;++i) {
            scanf("%d", &wi);
            int ans = query(1,1,h,wi);
            printf("%d\n", ans);
        }
    }
    return 0;
}