hdu 2795 线段树

比较简单的线段树，查询的时候如果左子树够的话就向左递归，否则向右递归，到叶子时终止。
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 200001;
 7 int h, w, n;
 8 
 9 int max( int x, int y )
10 {
11     return x > y ? x : y;
12 }
13 
14 struct Node 
15 {
16     int l, r, maxn;
17 } node[N << 2];
18 
19 void build( int i, int l, int r )
20 {
21     node[i].l = l, node[i].r = r, node[i].maxn = w;
22     if ( l == r ) return ;
23     int mid = ( l + r ) >> 1;
24     build( i << 1, l, mid );
25     build( i << 1 | 1, mid + 1, r );
26 }
27 
28 int query( int i, int len )
29 {
30     if ( node[i].l == node[i].r ) 
31     {
32         node[i].maxn -= len;
33         return node[i].l;
34     }
35     int r;
36     if ( node[i << 1].maxn >= len ) 
37     {
38         r = query( i << 1, len );
39     }
40     else
41     {
42         r = query( i << 1 | 1, len );
43     }
44     node[i].maxn = max( node[i << 1].maxn, node[i << 1 | 1].maxn );
45     return r;
46 }
47 
48 int main ()
49 {
50     while ( scanf("%d%d%d", &h, &w, &n) != EOF )
51     {
52         if ( h < n ) build( 1, 1, h );
53         else build( 1, 1, n );
54         for ( int i = 1; i <= n; i++ )
55         {
56             int len;
57             scanf("%d", &len);
58             if ( node[1].maxn < len )
59             {
60                 printf("-1
");
61             }
62             else
63             {
64                 int ans = query( 1, len );
65                 printf("%d
", ans);
66             }
67         }
68     }
69     return 0;
70 }