HDU 2795 Billboard（线段树查询区间最大值）

思路：

1.采用线段树存储区间最大值；
2.左子树和右子树均满足条件时优先选择左子树；
3.区间长度取min(h,n)即可，直接取h数组开不到那么大；
4.注意边界情况，即区间长度为1，此时线段树只有第0个值，在查询到的下标>h-1时不可直接返回，应该判断该点是不是真的大于（等于）我们要查询的值；

代码：

#include<iostream>
#include<algorithm>
using namespace std;
template <class T>
inline bool read(T &ret){
	char c; int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn; return 1;
}
inline void out(int x){
	if(x>9) out(x/10); putchar(x%10+'0');
}
const int MAX_N=2e5+99;
int h,w,n,H;
int dat[MAX_N<<2];
void init_ST(int n_){
	h=1;
	while(h<n_) h<<=1;
	for(int i=0;i<(h<<1)-1;i++) dat[i]=w;
}
void update(int k,int a){    //将第k(0-indexed)个值减去a 
	k+=h-1;
	dat[k]-=a;
	while(k>0){
		k=(k-1)>>1;
		dat[k]=max(dat[(k<<1)+1],dat[(k<<1)+2]);
	} 
}
int query(int k,int val){
	if(k>=h-1){
		if(k-h+1>H||dat[k]<val) return -1;
		else return k-h+1;
	}
	if(dat[k]<val) return -1;
	int l=(k<<1)+1,r=(k<<1)+2;
	if(dat[l]>=val) return query(l,val);
	else return query(r,val);
}
int main(){
	while(read(h)&&read(w)&&read(n)){
		H=h-1; init_ST(min(h,n));
		while(n--){
			int w; read(w);
			int rs=query(0,w);
			if(~rs){
				out(rs+1); putchar('
');
				update(rs,w);
			}else puts("-1");
		}
	}
	return 0;
}