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

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