HDU 2795 Billboard(线段树)

       题意是有一张n*m的广告牌，然后有t张1*xi的广告，每张广告都尽量往上往左贴，然后输出第xi张广告所在的行数，如果贴不下的话就输出-1。

      思路就是初始化每个结点为m值，表示可以贴长度为m的广告，然后Pushup函数维护一个区间的最大值，然后贴广告的时候优先贴左节点就好了。不懂的可以问。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
#define maxn 200005
using namespace std;
int sum[maxn << 2],pre[maxn];
int n,m,T;
string str;

void Pushup(int o){
  sum[o] = max(sum[o << 1] , sum[o << 1 | 1]);
}

void Build(int l, int r, int o){
  if(l == r){
    sum[o] = m;
    return ;
  }
  int mid = (l + r) >> 1;
  Build(lson);
  Build(rson);
  sum[o] = m;
}

void Query(int x, int l, int r, int o){
  if(x > sum[o]){
    printf("-1\n");
    return ;
  }
  if(l == r){
    sum[o] -= x;
    printf("%d\n",r);
    return ;
  }
  int mid = (l + r) >> 1;
  int ans = 0;
  if(x <= sum[o << 1]) Query(x, lson);
  else{
    Query(x, rson);
  }
  Pushup(o);
}

int main()
{
  while(~scanf("%d%d%d",&n,&m,&T)){
    int t = min(T,n);
    Build(1,t,1);
    for(int i=0;i<T;i++){
      int x;
      scanf("%d",&x);
      Query(x,1,t,1);
    }
  }
  return 0;
}