hdu2795(线段树单点更新&区间最值)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795

题意：有一个 h * w 的板子，要在上面贴 n 条 1 * x 的广告，在贴第 i 条广告时要尽量将其靠上贴，并输出其最上能贴在哪个位置；

思路：可以将每行剩余空间大小存储到一个数组中，那么对于当前 1 * x 的广告，只需找到所有剩余空间大于的 x 的行中位置最小的即可；

不过本题数据量为 2e5，直接暴力因该会 tle．可以用个线段树维护一下区间最大值，然后查询时对线段树二分即可；

代码：

 #include <iostream>

 #include <stdio.h>

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 using namespace std;

 const int MAXN = 2e5 + ;

 int Max[MAXN << ], h, w, n;

 int max(int a, int b){

     return a > b ? a : b;

 }

 void push_up(int rt){

     Max[rt] = max(Max[rt << ], Max[rt <<  | ]);

 }

 void build(int l, int r, int rt){//建树

     Max[rt] = w;

     if(l == r) return;

     int mid = (l + r) >> ;

     build(lson);

     build(rson);

 }

 void update(int p, int x, int l, int r, int rt){//单点更新

     if(l == r){

         Max[rt] -= x;

         return;

     }

     int mid = (l + r) >> ;

     if(p <= mid) update(p, x, lson);

     else update(p, x, rson);

     push_up(rt);

 }

 int query(int x, int l, int r, int rt){//查询

      if(l == r) return l;

      int mid = (l + r) >> ;

      int ans = ;

      if(Max[rt << ] >= x) ans = query(x, lson);

      else ans = query(x, rson);

      return ans;

 }

 int main(void){

     while(~scanf("%d%d%d", &h, &w, &n)){

         if(h > n) h = n;

         build(, h, );

         while(n--){

             int x, cnt;

             scanf("%d", &x);

             if(Max[] < x){

                 printf("-1\n");

                 continue;

             }else printf("%d\n", cnt = query(x, , h, ));

             update(cnt, x, , h, );

         }

     }

     return ;

 }

其实这个代码中的更新的路径和查询的路径是一样的，可以优化一下，将更新写进查询里面去；

优化代码：

 #include <iostream>

 #include <stdio.h>

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 using namespace std;

 const int MAXN = 2e5 + ;

 int Max[MAXN << ], h, w, n;

 int push_up(int rt){

     Max[rt] = max(Max[rt << ], Max[rt <<  | ]);

 }

 void build(int l, int r, int rt){

     Max[rt] = w;

     if(l == r) return;

     int mid = (l + r) >> ;

     build(lson);

     build(rson);

 }

 int query(int x, int l, int r, int rt){

     if(l == r){

         Max[rt] -= x;

         return l;

     }

     int mid = (l + r) >> ;

     int cnt = (Max[rt << ] >= x) ? query(x, lson) : query(x, rson);

     push_up(rt);

     return cnt;

 }

 int main(void){

     while(~scanf("%d%d%d", &h, &w, &n)){

         if(h > n) h = n;

         build(, h, );

         while(n--){

             int x;

             scanf("%d", &x);

             if(Max[] < x) printf("-1\n");

             else printf("%d\n", query(x, , h, ));

         }

     }

     return ;

 }

巴特西

hdu2795(线段树单点更新&区间最值)

最新文章

热门文章