HDU 2795 Billboard（线段树）
最后更新于：2022-04-01 15:53:07
题目链接：[点击打开链接](http://acm.hdu.edu.cn/showproblem.php?pid=2795)
题意： 原始序列全为w， 找到最左边的>=a的位置， 将该位置的值减去a，答案为该位置， 如果找不到符合要求的位置， 输出-1。
该题利用线段树递归特点来求其最左边的大于等于a的位置。
线段树递归的特点是从祖先结点开始自顶向下递归，访问各个元素的顺序一定是从左到右， 并且在递归之后可以顺便维护区间结点的值。
利用这个特点， 我们可以直接查询到>=a的最左边的位置。该元素变成v - a， 然后顺便维护改变了的值。 所以该题就成了维护区间最大值的线段树题目。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 200010;
int T,n,w,h,a,m,maxv[maxn*4];
void push_up(int o) {
maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
}
void build(int l, int r, int o) {
int m = (l + r) >> 1;
maxv[o] = w;
if(l == r) return ;
build(l, m, o<<1);
build(m+1, r, o<<1|1);
push_up(o);
}
int query(int v, int l, int r, int o) {
int m = (l + r) >> 1, ans = 0;
if(l == r) {
maxv[o] -= v; return l;
}
if(maxv[o<<1] >= v) ans = query(v, l, m, o<<1);
else ans = query(v, m+1, r, o<<1|1);
push_up(o);
return ans;
}
int main() {
while(~scanf("%d%d%d",&h,&w,&n)) {
if(h > n) h = n;
build(1, h, 1);
for(int i=0;i<n;i++) {
scanf("%d",&a);
if(maxv[1] < a) printf("-1\n");
else printf("%d\n",query(a, 1, h, 1));
}
}
return 0;
}
~~~