线段树 Ⅱ

朴灿烈づ我的快乐病毒、 2022-08-03 13:45 289阅读 0赞

单点修改（内容有升级）  
\[hdu2795\] ([http://acm.hdu.edu.cn/showproblem.php?pid=2795][http_acm.hdu.edu.cn_showproblem.php_pid_2795])  
题目描述：  
Billboard（公告板）

Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 15079 Accepted Submission(s): 6421

Problem Description  
At the entrance to the university, there is a huge rectangular（矩形的） billboard of size h\*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information.

On September 1, the billboard was empty. One by one, the announcements started being put on the billboard.

Each announcement is a stripe（条纹） of paper of unit（单元） height. More specifically, the i-th announcement is a rectangle（矩形） of size 1 \* wi.

When someone puts a new announcement on the billboard, she would always choose the topmost（最高） possible position for the announcement. Among all possible topmost positions she would always choose the leftmost（最左） one.

If there is no valid location for a new announcement, it is not put on the billboard (that’s why some programming contests have no participants from this university).

Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed.

Input  
There are multiple cases (no more than 40 cases).

The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions（规模，大小） of the billboard and the number of announcements.

Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement.

Output  
For each announcement (in the order they are given in the input file) output one number - the number of the row in which this announcement is placed. Rows（行数） are numbered from 1 to h, starting with the top row. If an announcement can’t be put on the billboard, output “-1” for this announcement.

Sample Input  
3 5 5  
2  
4  
3  
3  
3

Sample Output  
1  
2  
1  
3  
\-1  
分析：  
题目大意是给一个h\*w的公告牌，h是高度，w是宽度，一个单位高度1为一行，然后会有一些公告贴上去，公告是1\*wi大小的长纸条，优先贴在最上面并且最左边的位置，如果没有空间贴得下，就输出-1，可以的话，就输出所贴的位置（第几行）。  
叶节点\[x,x\]表示board的第x行还可以放置的长度，区间\[a，b\]表示第a行到b行中剩下空间最大的那一行是多少，如果要把长w的公告放入 board时就是update，优先往左子树走（如果左子树的空间足够的话），一直走到叶节点，更新这个叶节点剩下的长度，然后再向上更新。

#include <iostream>
    #include <stdio.h>
    
    using namespace std;
    
    const int N=200005;
    int w;
    struct node
    {
        int l,r,mid;//表示左端点，右端点，中点
        int ma;//表示节点内的最大值
    }tree[N*4];
    
    int max(int a,int b)
    {
        return a>b ? a:b;
    }
    int min(int a,int b)
    {
        return a<b ? a:b;
    }
    
    void build(int l,int r,int root)
    {
        tree[root].l=l;
        tree[root].r=r;
        tree[root].mid=(l+r)/2;
        tree[root].ma=w;//选宽度为节点内的最大值
        if(l==r)//建立递归到叶子节点
        {
            return;
        }
        build(l,(l+r)/2,root<<1);//建立左儿子直到叶子节点
        build((l+r)/2+1,r,root<<1|1);//建立右儿子直到叶子节点
    }
    
    int updata(int board,int root)
    {
        if(tree[root].l==tree[root].r)//表示当前公告板上第l行还能放置的长度
        {
            tree[root].ma-=board;//将广告单的长度减去
            return tree[root].l;
        }
        int ret;
        if(tree[root<<1].ma>=board)//优先在左儿子中找到空位，并把它放下
        {
            ret=updata(board,root<<1);
        }
        else ret=updata(board,root<<1|1);
        tree[root].ma=max(tree[root<<1].ma,tree[root<<1|1].ma);
        return ret;
    }
    
    int main()
    {
        int h,n,a;
        while(scanf("%d%d%d",&h,&w,&n)!=EOF)
        {
            build(1,min(h,n),1);//取h和n的最小值，作为右端点，从root=1开始来建树
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a);
                if(tree[1].ma<a) printf("-1\n");
                else printf("%d\n",updata(a,1));
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_2795]: http://acm.hdu.edu.cn/showproblem.php?pid=2795