HDU 2795 Billboard

线段树，保存区间最大值，从顶端下来，优先往左边走，确定位置，然后更新。

/* ***********************************************
Author        :Zhou Zhentao
Email         :774388357@qq.com
Created Time  :2015/11/21 9:45:58
File Name     :acm.cpp
************************************************ */
#include <iostream>  
#include <cstdio>  
#include <cmath>  
  
  
using namespace std;  
  
#define MAXN 200000+10
#define INF 0x7fffffff  
  
int A[MAXN];  
int v[MAXN];
int Wnow[MAXN];
//int max;  
//int min;  
  
struct node  
{  
    int left;  
    int right;  
    int max;           //维护最大值  
    int sum;          //维护区间和  
    int min;           //维护最小值  
}Tree[MAXN<<2];  

int h,w,n;
  
void maintain(int root)         //向上调整  
{  
    int LC = root<<1;  
    int RC = (root<<1)+1;  
    Tree[root].sum = Tree[LC].sum + Tree[RC].sum;  
    Tree[root].max = max(Tree[LC].max,Tree[RC].max);  
    Tree[root].min = min(Tree[LC].min,Tree[RC].min);  
}  
  
void Build(int root,int start,int end)                     //构建线段树  
{  
    Tree[root].left = start;  
    Tree[root].right = end;  
    if(start == end)  
    {  
        Tree[root].sum = Wnow[start];  
        Tree[root].max = Wnow[start];  
        Tree[root].min = Wnow[start];  
        return;
    }  
    int mid = (start + end)>>1;  
    Build(root<<1,start,mid);  
    Build((root<<1)+1,mid+1,end);  
    maintain(root);  
}  
  
void update(int root,int pos,int value)                     //更新点的值  
{  
    if(Tree[root].left == Tree[root].right && Tree[root].left == pos)  
    {  
        Tree[root].sum += value;  
        Tree[root].max += value;  
        Tree[root].min += value;  
        return;  
    }  
    int mid = (Tree[root].left + Tree[root].right)>>1;  
    if(pos <= mid)  
        update(root<<1,pos,value);  
    else  
        update((root<<1)+1,pos,value);  
    maintain(root);  
}  
  
int Query(int root,int start,int end)                         //查询区间和  
{  
    if(start == Tree[root].left && Tree[root].right == end)  
    {  
        return Tree[root].sum;  
    }  
    int mid = (Tree[root].left + Tree[root].right)>>1;  
    int ret = 0;  
    if(end <= mid)  
        ret += Query(root<<1,start,end);  
    else if(start >= mid+1)  
        ret += Query((root<<1)+1,start,end);  
    else  
    {  
        ret += Query(root<<1,start,mid);  
        ret += Query((root<<1)+1,mid+1,end);  
    }  
    return ret;  
}  
  
int RminQ(int root,int start,int end)              //查询区间最小值  
{  
    if(start == Tree[root].left && Tree[root].right == end)  
    {  
        return Tree[root].min;  
    }  
    int mid = (Tree[root].left + Tree[root].right)>>1;  
    int ret = INF;  
    if(end <= mid)  
        ret = min(ret,RminQ(root<<1,start,end));  
    else if(start >= mid+1)  
        ret = min(ret,RminQ((root<<1)+1,start,end));  
    else  
    {  
        int a = RminQ(root<<1,start,mid);  
        int b = RminQ((root<<1)+1,mid+1,end);  
        ret = min(a,b);  
    }  
    return ret;  
}  
  
int RmaxQ(int root,int start,int end)                 //查询区间最大值  
{  
    if(start == Tree[root].left && Tree[root].right == end)  
    {  
        return Tree[root].max;  
    }  
    int mid = (Tree[root].left + Tree[root].right)>>1;  
    int ret = 0;    //modify this  
    if(end <= mid)  
        ret = max(ret,RmaxQ(root<<1,start,end));  
    else if(start >= mid+1)  
        ret = max(ret,RmaxQ((root<<1)+1,start,end));  
    else  
    {  
        int a = RmaxQ(root<<1,start,mid);  
        int b = RmaxQ((root<<1)+1,mid+1,end);  
        ret = max(a,b);  
    }  
    return ret;  
}  


int main()
{
    while(~scanf("%d%d%d",&h,&w,&n))
    {
        for(int i=1;i<=n;i++) scanf("%d",&v[i]);
           for(int i=1;i<=min(h,n);i++) Wnow[i]=w;

        Build(1,1,min(h,n));

        for(int i=1;i<=n;i++)
        {
            if(Tree[1].max<v[i]) 
            {
                   printf("-1
");
                continue;
            }
            int now=1;
               while(1)
            {
                if(Tree[now].left==Tree[now].right)
                {
                    printf("%d
",Tree[now].left);
                    update(1,Tree[now].left,-v[i]);
                    break;
                }
                else
                {
                    if(Tree[now<<1].max>=v[i]) now=(now<<1);
                    else now=(now<<1)+1;
                }
            }
        }
    }
    return 0;
}