hdu2795 Billboard(线段树单点修改)

结点中的l和r表示层数，maxx表示这层最多还剩下多少宽度。根据公告的宽度取找到可以放的那一层

找到后返回层数，并修改maxx

 1 #include<bits/stdc++.h> 
 2 using namespace std;
 3 const int maxn= 200000+5;
 4 int h,w;
 5 int ans;
 6 struct Node
 7 {
 8     int l,r,maxx;//l和r是层数，maxx是每层还有多少空位 
 9 } node[maxn<<2];
10 void PushUp(int k)
11 {
12     node[k].maxx=max(node[k<<1].maxx,node[k<<1|1].maxx);
13 }
14 void BuildTree(int l,int r,int k)
15 {
16     node[k].l=l;
17     node[k].r=r;
18     node[k].maxx=w;
19     //因为初始是每个节点的最大值均为w
20     //所以可以省去PushUp(k);
21     if(l==r)
22     {
23         return;
24     }
25     int mid=(l+r)>>1;
26     BuildTree(l,mid,k<<1);
27     BuildTree(mid+1,r,k<<1|1);
28     //PushUp(k);
29 }
30 void UpdateTree(int i,int x)
31 {
32     if(node[i].l==node[i].r)
33     {
34         node[i].maxx-=x;
35         ans=node[i].l;
36         return;
37     }
38     if(x<=node[i<<1].maxx)
39         UpdateTree(i<<1,x);//往左边找，左边层数比较低（因为他要尽量放在最上面） 
40     else
41         UpdateTree(i<<1|1,x);
42     PushUp(i);
43 }
44 int main()
45 {
46     int n;
47     while(cin>>h>>w>>n)
48     {
49         if(h>n)
50             h=n;
51         //根据题意，因为最多放n个公告，
52         //占用的最大高度也只有n，优化建树的高度
53         BuildTree(1,h,1);
54         int x;
55         while(n--)
56         {
57             ans=-1;
58             scanf("%d",&x);
59             if(node[1].maxx>=x)
60                 UpdateTree(1,x);//每次都从第一层开始找 
61             printf("%d
",ans);
62         }
63     }
64     return 0;
65 }

View Code