【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

题意：给一个矩阵，每次询问有个高度为1的小矩阵，要每次尽量往左上方插入，如果有位置输出对应行，若无则输出“-1”

思路（线段树+区间最值）：

1.可能乍一看这题目，很多人都会第一感觉：“这能和线段树扯上关系？”，诚然，这个矩阵嵌套的二维模型怎么会和一维的查询修改有关呢？但是，仔细读题，有两个关键点

输入的小矩阵高度为1

且只用输出所在行数（题目里的高度）

2.这有什么作用呢？说明这个大矩阵所谓的第二维高度，根本没有限制性因素。

如图，表示一个三行四列的矩阵，我把每行切分成一个单位的相同长度矩阵

它可以看成一个由三行拼接起来的单个一维矩阵

那么原问题就转化成了

在这个一维矩阵中，尽量往左端填，输出时返回第几“块”。

这里的块就是由原来的行数决定的，如图，就是3块。那么就相当于每块都有相同的“容量”，然后我们尽量往左边容量够的地方填充。这时候，细心的你已经发现了，这不就是一个个区间吗？是的，一个如图所示的区间

长度为3的一个数组，下标1->3，每个元素的大小都是原矩阵列数（即“容量”）。
这下，问题变得熟悉了起来，我要在某个下标位置放一个value，要使得尽量往左放，放完更新对应元素大小。这不就是一个区间最值问题了吗？我每次有左右子树可选，我要尽量往左，好吧，那就左子树优先，当前结点存放一个当前区间内的容量最大值，这样我只要在满足最大值大于等于要塞进去的元素的情况下，尽量往左走就行了。到达要放的点就返回更新。
em。。。大概就这么多吧。其实是个水题hh

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <limits.h>
#define maxn 1000000+500
using namespace std;
typedef long long ll;
typedef struct Tree
{
    int l;
    int r;
    int maxone;
    int lazy;
} T;
T a[maxn];
int num[maxn];
int n,m,q;


inline int read()
{
    int x = 0;
    char ch;
    ch = getchar();
    while(ch<'0'||ch>'9')
        ch = getchar();
    while(ch>='0'&&ch<='9')
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }
    return x;
}

void update(int k)
{
    a[k].maxone = max(a[k<<1].maxone, a[k<<1|1].maxone);
}

void build_tree(int l, int r, int k)
{
    a[k].l = l;
    a[k].r = r;
    if(l==r)
    {
        a[k].maxone = m;
        return ;
    }
    int mid = (l+r)>>1;
    build_tree(l,mid,k<<1);
    build_tree(mid+1,r,k<<1|1);
    update(k);
}
int flag = 0;
int ans = 0;
void  change_for_one(int k,int val)
{
    if(a[k].l==a[k].r)
    {
        a[k].maxone -= val;
        if(a[k].maxone>=0)
            flag = 1;
        ans = a[k].l;
        return ;
    }
    if(a[k<<1].maxone>=val)
        change_for_one(k<<1,val) ;
    else if(a[k<<1|1].maxone>=val)
        change_for_one(k<<1|1,val);
    update(k);
}

int main()
{
    while(~scanf("%d",&n))
    {
        m = read();
        q = read();
        n = min(n,q);
        build_tree(1,n,1);
        for(int i=1; i<=q; ++i)
        {
            int x;
            x = read();
            flag = 0;
            change_for_one(1,x);
            if(flag)
                printf("%d\n",ans);
            else
                printf("-1\n");
        }
    }
    return 0;
}