Billboard

hdu2795:http://acm.hdu.edu.cn/showproblem.php?pid=2795

题意：给一个h*w的公告牌，h是高度，w是宽度，一个单位高度1为一行，然后会有一些公告贴上去，公告是1*wi大小的长纸条，优先贴在最上面并且最左边的位置，如果没有空间贴得下，就输出-1，可以的话，就输出所贴的位置（第几行）。
 题解：用线段树来维护。把高度看成每一个节点，即每一行看成线段树的一个节点，而w看成底层节点的值，然后每个节点维护区间的最大值。由于h会达到10的9次方，但是只有200000的海报。随意当h大于200000时候，只需建立n==200000的树。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int h,w,post,num,temp;//记录高度，长度，海报的数量，

 struct Node{

     int left;

     int right;

     int maxn;//区间的最大值

     int id;//底层的点的序号，用来标记行数

 }node[*];

 void build(int l,int r,int idx){

     node[idx].left=l;

     node[idx].right=r;

     node[idx].id=;

     if(l==r){

         node[idx].maxn=w;

         node[idx].id=num++;//逐步记录

         return;

     }

     int mid=(l+r)/;

     build(l,mid,idx<<);

     build(mid+,r,idx<<|);

     node[idx].maxn=max(node[idx<<].maxn,node[idx<<|].maxn);//pushup上去

 }

 void update(int value,int idx){

     if(node[idx].left==node[idx].right){//如果到达底层的点

         if(node[idx].maxn>=value){//如果满足要求，则更新节点的值

          node[idx].maxn-=value;

          printf("%d\n",node[idx].id);//输出行号

         }

     return;

     }

     if(node[idx<<].maxn>=value)update(value,idx<<);//如果左儿子的manx满足要求，则优先考虑左边

     else if(node[idx<<|].maxn>=value)update(value,idx<<|);//如果左边不满足，右边满足则进入右儿子

     else {//否则则没有空间，输出-1，并且返回

     printf("-1\n");

     return ;

     }

     node[idx].maxn=max(node[idx<<].maxn,node[idx<<|].maxn);//更新父节点的maxn

 }

 int main(){

     while(~scanf("%d%d%d",&h,&w,&post)){//多组数据

         num=;//初始化

      if(h<=)build(,h,);

      else    build(,,);

     for(int i=;i<=post;i++){

         scanf("%d",&temp);

         update(temp,);

      }

     }

 }