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;
}