題目：HDU2795 Billboard

#include <stdio.h> #define maxn 222222#define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1int w,h,n; int MAX[maxn<<2];int max(int a,int b) {return a>b? a:b; }void PushUP(int rt) {MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]); }void Build(int l,int r,int rt) {MAX[rt]=w;if(l==r)return;int m=(l+r)>>1;Build(lson);Build(rson); }int Query(int x,int l,int r,int rt) {if(l==r){MAX[rt]-=x;return r;}int m=(l+r)>>1;int ret=(MAX[rt<<1]>=x)? Query(x,lson):Query(x,rson);PushUP(rt);return ret; }int main() {while(~scanf("%d%d%d",&h,&w,&n)){if(h>n) h=n;Build(1,h,1);while(n--){int x;scanf("%d",&x);if(MAX[1]<x)puts("-1");elseprintf("%d\n",Query(x,1,h,1));}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的线段树空间容纳且最上边的数(单点更新)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。