1 /* 2     主要利用线段树求区间最值，sum[]代表位置可用空间 3     每次找到最大值的位置 4     功能：查询最靠前能容纳广告的位置 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #define lson l, m, rt << 110 #define rson m+1, r, rt << 1 | 111 12 const int MAX_N = 2000000 + 10;13 int w[MAX_N];14 int num[MAX_N];15 int sum[MAX_N << 2];16 int n, h, W;17 18 void maxsum(int rt)19 {20     sum[rt] = std::max (sum[rt << 1], sum[rt << 1 | 1]);21 }22 23 void build(int l, int r, int rt)24 {25     sum[rt] = W;26     if (l == r) return ;27     int m = (l + r) >> 1;28     build (lson);29     build (rson);30 }31 32 int query(int p, int l, int r, int rt)33 {34     if (l == r)35     {36         sum[rt] -= p;        //如果可以用，更新sum，update在query里做了37         return l;            //返回该位置38     }39     int m = (l + r) >> 1;40     int ans;41     if (p <= sum[rt << 1])        //如果p小于左孩子的最大值，则往左边下去42         ans = query (p, lson);43     else44         ans = query (p, rson);45     maxsum (rt);46 47     return ans;48 }49 50 int main(void)        //HDOJ 2795 Billboard51 {52     //freopen ("inD.txt", "r", stdin);53 54     while (~scanf ("%d%d%d", &h, &W, &n))55     {56         if (h > n)        // h <= n57             h = n;58 59         build (1, h, 1);60 61         int x;62         while (n--)63         {64             scanf ("%d", &x);65             if (x > sum[1])    printf ("%d\n", -1);    //所有位置的最大值66             else    printf ("%d\n", query(x, 1, h, 1));67         }68     }69 70     return 0;71 }