hdu2795 Billboard

http://acm.hdu.edu.cn/showproblem.php?pid=2795

线段树，单点更新

好题，查询属于全区间的单点查询，目标值：准备贴的海报宽度

如果左子树的最大值比目标值大，则优先查且只查左子树（我们想要得到编号最小且满足条件的行贴海报）

否则查右子树，如果左右子树的最大值，都比目标值小，就返回-1（没地方贴了～）

WA了一次，没考虑高度为1的展板。

 1 #include <stdio.h>
 2 
 3 #define lson l, m, root<<1
 4 #define rson m+1, r, root<<1|1
 5 
 6 const int maxn = 200010;
 7 int max1[maxn<<2];
 8 
 9 int max(int x, int y)
10 {
11     return x>y? x: y;
12 }
13 
14 void push_up(int root)
15 {
16     max1[root] = max(max1[root<<1], max1[root<<1|1]);
17 }
18 
19 void build(int x, int l, int r, int root)
20 {
21     int m;
22     if(l == r)
23     {
24         max1[root] = x;
25         return;
26     }
27     m = (l + r) >> 1;
28     build(x, lson);
29     build(x, rson);
30     push_up(root);
31 }
32 
33 void update(int x, int sub, int l, int r, int root)
34 {
35     int m;
36     if(l == r)
37     {
38         max1[root] -= sub;
39         return;
40     }
41     m = (l + r) >> 1;
42     if(x <= m)
43     {
44         update(x, sub, lson);
45     }
46     if(m+1 <= x)
47     {
48         update(x, sub, rson);
49     }
50     push_up(root);
51 }
52 
53 int query(int x, int l, int r, int root)
54 {
55     int m;
56     if(l == r)
57     {
58         if(max1[root] >= x)
59         {
60             return l;
61         }
62         return -1;
63     }
64     m = (l + r) >> 1;
65     if(max1[root<<1] >= x)
66     {
67         return query(x, lson);
68     }
69     if(max1[root<<1|1] >= x)
70     {
71         return query(x, rson);
72     }
73     return -1;
74 }
75 
76 int main()
77 {
78     int n, w, h, a, temp;
79     while(~scanf("%d%d%d", &h, &w, &n))
80     {
81         if(n < h)
82         {
83             h = n;
84         }
85         build(w, 1, h, 1);
86         while(n-- && scanf("%d", &a))
87         {
88             temp = query(a, 1, h, 1);
89             printf("%d\n", temp);
90             if(~temp)
91             {
92                 update(temp, a, 1, h, 1);
93             }
94         }
95     }
96     return 0;
97 }