HDU 2795 Billboard

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

题意：

在大学入口处，有一个巨大的长方形广告牌，大小h * w（h是其高度，w是其宽度）。董事会是所有可能的公告发布的地方：最近的节目竞赛，餐厅菜单的变化，以及其他重要信息。
9月1日，广告牌是空的。一个接一个地，公告开始放在广告牌上。
每个公告是一个单位高度的纸条。更具体地，第i个通知是大小为1 * wi的矩形。
当有人在广告牌上放置新的公告时，她总是会选择公告的最高位置。在所有可能的最高职位中，她总是选择最左边的一个。
如果新公告没有有效位置，它不会放在广告牌上（这就是为什么一些编程竞赛没有来自这所大学的参与者）。
考虑到广告牌和公告的大小，您的任务是找到放置公告的行数。

思路：

用线段树来做，每个结点维护3个值l，r，w。代表第l行到第r行之间最大的剩余宽度为w。之后就是查询和更新了。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 200000 + 5;;
 7 
 8 int h, w, n;
 9 int ans;
10 
11 struct node
12 {
13     int l, r, w;
14 }t[4*maxn];
15 
16 void build(int L,int R,int k)
17 {
18     t[k].l = L;
19     t[k].r = R;
20     t[k].w = w;
21     if (L == R)  return;
22     int mid = (L + R) / 2;
23     build(L, mid, 2 * k);
24     build(mid + 1, R, 2 * k + 1);
25 }
26 
27 
28 void update(int cow, int x,int k)
29 {
30     if (t[k].l == t[k].r && t[k].l==cow)
31     {
32         t[k].w -= x;
33         return;
34     }
35     int mid = (t[k].l + t[k].r) / 2;
36     if (cow <= mid)  update(cow, x, 2 * k);
37     else   update(cow, x, 2 * k + 1);
38     t[k].w = max(t[2 * k].w, t[2 * k + 1].w);
39 }
40 
41 void query(int x, int k)
42 {
43     if (t[k].w < x)  return;
44     if (t[k].l == t[k].r)
45     {
46         if (t[k].w >= x)
47         {
48             ans = t[k].l;
49             return;
50         }
51     }
52     int lc = 2 * k, rc = 2 * k + 1;
53     if (t[lc].w >= x)  query(x, lc);
54     else if (t[rc].w >= x)  query(x, rc);
55     else return;
56 }
57 
58 int main()
59 {
60     //freopen("D:\txt.txt", "r", stdin);
61     int x;
62     while (~scanf("%d%d%d",&h,&w,&n))
63     {
64         if (h > n)   h = n;
65         build(1,h,1);
66         while (n--)
67         {
68             ans = -1;
69             scanf("%d", &x);
70             query(x, 1);
71             if (ans != -1)
72             {
73                 printf("%d
", ans);
74                 update(ans, x ,1);
75             }
76             else
77             {
78                 printf("-1
");
79             }
80         }
81     }
82 }