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

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <map>
 4 #include <queue>
 5 #include <string>
 6 #include <stack>
 7 #include <vector>
 8 #include <list>
 9 #include <cstdio>
10 #include <cstring>
11 #include <cmath>
12 using namespace std;
13 #define ll long long
14 #define pb push_back
15 #define fi first
16 #define se second
17 
18 const int N = 2e5+10;
19 int a[N],c[N];
20 int n,h,w;
21 
22 inline int lb(int x){
23     return x&(-x);
24 }
25 
26 void update(int inx){
27     for(int i = inx; i <= h; i += lb(i)){
28         c[i] = a[i];
29         int d = lb(i);
30         if(d == 1) continue;
31         for(int j = 1; j < d; j <<= 1)
32             c[i] = max(c[i], c[i-j]);
33     }
34 }
35 
36 inline bool fun(int& l,int& r,int it){
37     while(r <= h){
38      //   cout << "fun" << endl;
39         if(c[r] < it){
40             l = r;
41             r += lb(r);
42             if(r > h) r = l+1;//要遍历所有的分块区间
43         }
44         else return 1;
45     }
46     return 0;
47 }
48 
49 void solve(){
50     while(~scanf("%d%d%d",&h,&w,&n)){
51         h = h >= n ? n : h;
52         for(int i = 1; i <= h; ++i) a[i] = c[i] = w;//初始化
53         int it;
54         for(int p = 1; p <= n; ++p){
55             scanf("%d",&it);
56             int l = 1,r = 1,ok = 0;
57             while(fun(l,r,it)){//找是否有满足的区间
58                // cout << "main" << endl;
59                 ok = 1;
60                 if(l == r){
61                     printf("%d\n",l);
62                     a[l] -= it;
63                     update(l);
64                     break;  
65                 }
66                 else r = ++l;//缩小区间
67             }
68             if(!ok) printf("-1\n");
69         } 
70     }
71 }
72 
73 int main(){
74  
75   //  ios::sync_with_stdio(false);
76   //  cin.tie(0); cout.tie(0);
77     solve();
78 
79     return 0;
80 }