Billboard HDU - 2795（树状数组，单点修改，区间查询）

题目链接：https://vjudge.net/problem/HDU-2795

思路：h = 1e9行不通，因为广告是1*w的，所以n个广告最多只需要 h = n的高度，那么h=2e5就可以接受了。

用树状数组维护区间最大值。

从前往后区间查询哪一大块块首先满足条件，然后一直缩小区间，直到区间长度等于1，输出答案，然后修改该点可用的w，

再修改区间最大值。

 #include <iostream>

 #include <algorithm>

 #include <map>

 #include <queue>

 #include <string>

 #include <stack>

 #include <vector>

 #include <list>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 using namespace std;

 #define ll long long

 #define pb push_back

 #define fi first

 #define se second

 const int N = 2e5+;

 int a[N],c[N];

 int n,h,w;

 inline int lb(int x){

     return x&(-x);

 }

 void update(int inx){

     for(int i = inx; i <= h; i += lb(i)){

         c[i] = a[i];

         int d = lb(i);

         if(d == ) continue;

         for(int j = ; j < d; j <<= )

             c[i] = max(c[i], c[i-j]);

     }

 }

 inline bool fun(int& l,int& r,int it){

     while(r <= h){

      //   cout << "fun" << endl;

         if(c[r] < it){

             l = r;

             r += lb(r);

             if(r > h) r = l+;//要遍历所有的分块区间

         }

         else return ;

     }

     return ;

 }

 void solve(){

     while(~scanf("%d%d%d",&h,&w,&n)){

         h = h >= n ? n : h;

         for(int i = ; i <= h; ++i) a[i] = c[i] = w;//初始化

         int it;

         for(int p = ; p <= n; ++p){

             scanf("%d",&it);

             int l = ,r = ,ok = ;

             while(fun(l,r,it)){//找是否有满足的区间

                // cout << "main" << endl;

                 ok = ;

                 if(l == r){

                     printf("%d\n",l);

                     a[l] -= it;

                     update(l);

                     break;

                 }

                 else r = ++l;//缩小区间

             }

             if(!ok) printf("-1\n");

         }

     }

 }

 int main(){

   //  ios::sync_with_stdio(false);

   //  cin.tie(0); cout.tie(0);

     solve();

     return ;

 }

Billboard HDU - 2795（树状数组，单点修改，区间查询）的相关教程结束。