題意：

給出一塊h*w的廣告牌，還有n張1*u的海報，海報盡量往上，左邊的位置張貼，問每一張海報能貼的多高。

線段樹單點修改。

注意：因為1 <= h,w <= 10^9; 1 <= n <= 200,000，但實際上，若h>n的話，最壞的情況下也只要用到前n行。

所以若h>n ?則h=n

如果不加這一句，因為線段樹的數組要開到h<<2這么大，又h<= 10^9，所以輸入的h過大時會使開的數組過大。加了的話，就不會啦，n<<2是OK的。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define lson l,m,rt<<1 5 #define rson m+1,r,rt<<1|1 6 const int maxh=200010; 7 int _max[maxh<<2]; 8 int ans; 9 void pushup(int rt) 10 { 11 _max[rt]=max(_max[rt<<1],_max[rt<<1|1]); 12 } 13 void query(int u,int l,int r,int rt) 14 { 15 if(l==r){ 16 _max[rt]-=u; 17 ans=l; 18 return ; 19 } 20 int m=(l+r)>>1; 21 if(_max[rt<<1]>=u) 22 query(u,lson); 23 else 24 query(u,rson); 25 pushup(rt); 26 } 27 int main() 28 { 29 int h,w,n; 30 while(scanf("%d%d%d",&h,&w,&n)!=EOF){ 31 if(h>n) 32 h=n; 33 for(int i=1;i<=(h<<2);i++) 34 _max[i]=w; 35 int u; 36 for(int i=0;i<n;i++){ 37 scanf("%d",&u); 38 if(_max[1]<u) 39 printf("-1\n"); 40 else{ 41 query(u,1,h,1); 42 printf("%d\n",ans); 43 } 44 } 45 } 46 return 0; 47 } View Code

?

轉載于:https://www.cnblogs.com/-maybe/p/4355771.html

總結

以上是生活随笔為你收集整理的hdu2795 Billboard 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。