HUD.2795 Billboard ( 线段树 区间最值 单点更新 单点查询 建树技巧)

题意分析

题目大意：一个h*w的公告牌，要在其上贴公告。

输入的是1*wi的w值，这些是公告的尺寸。

贴公告要满足的条件：

1. 尽量往上，同一高度尽量靠左。

2. 求第n个广告所在的行数。

3. 没有合适的位置贴了则输出-1。

建树技巧

首先看了一下数据范围h和w都在1e9，按照高度建树不太现实的。但是发现询问只有2e5,。仔细想一下如果h < 2e5， 我们用h建树，否则用n建树。原因是，每个高度只放一个公告牌，最多也就2e5,。

线段树操作

线段树维护区间最大值。线段树的每个叶子节点表示当前高度剩余的容量。

对于询问，根据当前要张贴公告牌的宽度，优先向左（如果可以的话），其次向右。到达叶子节点后，更新叶子节点的值，同时记下所张贴的行数，return回上一层后，别忘记pushup。

代码总览

#include <bits/stdc++.h>

#define nmax 200010

using namespace std;

struct Tree{

    int l,r,val;

    int mid(){

        return (l+r)>>1;

    }

};

Tree tree[nmax<<2];

int num[nmax<<2];

int h,w,n,ans;

void PushUp(int rt)

{

    tree[rt].val = max(tree[rt<<1].val , tree[rt<<1|1].val);

}

void Build(int l, int r, int rt)

{

    tree[rt].l = l; tree[rt].r = r;

    tree[rt].val = w;

    if(l == r){

        return;

    }

    Build(l,tree[rt].mid(),rt<<1);

    Build(tree[rt].mid()+1,r,rt<<1|1);

    PushUp(rt);

}

void UpdatePoint(int val, int rt)

{

    if(tree[rt].l == tree[rt].r){

        tree[rt].val -= val;

        ans = tree[rt].l;

        return;

    }

    if(tree[rt<<1].val >= val) UpdatePoint(val,rt<<1);

    else if(tree[rt<<1|1].val >= val) UpdatePoint(val,rt<<1|1);

    PushUp(rt);

}

int main()

{

    //freopen("in2795.txt","r",stdin);

    while(scanf("%d %d %d",&h,&w,&n) != EOF){

        int leaveinfo = min(h,n);

        Build(1,leaveinfo,1);

        int wide = 0;

        for(int i = 0;i<n;++i){

            scanf("%d",&wide);

            if(tree[1].val < wide) printf("-1\n");

            else{

                UpdatePoint(wide,1);

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

            }

        }

    }

    return 0;

}