hdu 2795 Billboard

第一眼看这题不知所云，现在已经能轻松分析，看样子这两天进步还是有的。这题h是10^9的，看起来有点吓人，但因为n只有20W，所以h是10^999也没用，当h很大时数据范围就被固定在n上了，这点要多谢chenan前辈的提醒。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 200005
 4 int tree[4*N],D;
 5 int max(int a,int b)
 6 {
 7     return a>b ?a :b;
 8 }
 9 void update(int n)
10 {
11     for(; n^1; n >>= 1)
12         tree[n>>1] = max(tree[n],tree[n^1]);
13 }
14 int search(int cur,int k)
15 {
16     int lc=cur<<1,rc=lc|1;
17     if(cur >= D)
18     {
19         tree[cur] -= k;
20         update(cur);
21         return cur-D+1;
22     }
23     if(tree[lc] >= k)
24         search(lc,k);
25     else if(tree[rc] >= k)
26         search(rc,k);
27     else return -1;
28 }
29 int main()
30 {
31     int h,w,n,i,k;
32     while(~scanf("%d%d%d",&h,&w,&n))
33     {
34         for(D = 1; D < h && D < N; D <<= 1);
35         memset(tree,0,sizeof(int ) *2*D);
36         for(i = 0; i < D && i < h; i++)
37             tree[D+i] = w;
38         for(i = D-1; i > 0; i--)
39             tree[i] = max(tree[i<<1],tree[i<<1|1]);
40         while(n--)
41         {
42             scanf("%d",&k);
43             printf("%d\n",search(1,k));
44         }
45     }
46     return 0;
47 }