HDU 2795 Billboard （线段树单点更新求区间最值）

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

题意

在矩形广告牌上塞广告，每个广告宽为w高为1，规则从上至下，从左至右塞，塞不进去输出-1

思路

对广告牌高度建线段树，维护高度区间剩余宽度最大值，线段树查找可以塞的位置，并更新那个位置的剩余宽度，注意到h可能很大，但其实n只有200000，所以我们最多只需要建200000就可以了，因为如果这200000的高度如果还塞不进去后面的肯定也塞不进去了。

 1 #define IO std::ios::sync_with_stdio(0);
 2 #include <bits/stdc++.h>
 3 #define iter ::iterator
 4 using namespace  std;
 5 typedef long long ll;
 6 typedef pair<ll,ll>P;
 7 #define pb push_back
 8 #define se second
 9 #define fi first
10 #define rs o*2+1
11 #define ls o*2
12 const int N=2e5+5;
13 int n,m,q,ans;
14 int maxv[N*4];
15 void build(int o,int l,int r){
16     if(l==r){
17         maxv[o]=m;
18         return;
19     }
20     int m=(l+r)/2;
21     build(ls,l,m);
22     build(rs,m+1,r);
23     maxv[o]=max(maxv[ls],maxv[rs]);
24 }
25 void query(int o,int l,int r,int v){
26     if(maxv[o]<v)return;
27     if(l==r&&maxv[o]>=v){
28         maxv[o]-=v;
29         ans=l;
30         return;
31     }
32     int m=(l+r)/2;
33     if(maxv[ls]>=v)query(ls,l,m,v);
34     else if(maxv[rs]>=v)query(rs,m+1,r,v);
35     maxv[o]=max(maxv[ls],maxv[rs]);
36 }
37 int main(){
38     while(~scanf("%d%d%d",&n,&m,&q)){
39         n=min(n,q);
40         build(1,1,n);
41         while(q--){
42             int x;
43             scanf("%d",&x);
44             ans=-1;
45             query(1,1,n,x);
46             printf("%d
",ans);
47         }
48     }
49 }