hdu2795 Billboard(线段树单点修改)

传送门

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

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

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn= +;

 int h,w;

 int ans;

 struct Node

 {

     int l,r,maxx;//l和r是层数，maxx是每层还有多少空位

 } node[maxn<<];

 void PushUp(int k)

 {

     node[k].maxx=max(node[k<<].maxx,node[k<<|].maxx);

 }

 void BuildTree(int l,int r,int k)

 {

     node[k].l=l;

     node[k].r=r;

     node[k].maxx=w;

     //因为初始是每个节点的最大值均为w

     //所以可以省去PushUp(k);

     if(l==r)

     {

         return;

     }

     int mid=(l+r)>>;

     BuildTree(l,mid,k<<);

     BuildTree(mid+,r,k<<|);

     //PushUp(k);

 }

 void UpdateTree(int i,int x)

 {

     if(node[i].l==node[i].r)

     {

         node[i].maxx-=x;

         ans=node[i].l;

         return;

     }

     if(x<=node[i<<].maxx)

         UpdateTree(i<<,x);//往左边找，左边层数比较低（因为他要尽量放在最上面）

     else

         UpdateTree(i<<|,x);

     PushUp(i);

 }

 int main()

 {

     int n;

     while(cin>>h>>w>>n)

     {

         if(h>n)

             h=n;

         //根据题意，因为最多放n个公告，

         //占用的最大高度也只有n，优化建树的高度

         BuildTree(,h,);

         int x;

         while(n--)

         {

             ans=-;

             scanf("%d",&x);

             if(node[].maxx>=x)

                 UpdateTree(,x);//每次都从第一层开始找

             printf("%d\n",ans);

         }

     }

     return ;

 }