codeforces 272C. Dima and Staircase（线段树）

题目链接

    题目很长，看加猜加谷歌翻译才看懂了题目。每级台阶的宽都是1，但高不同，并且告诉你了，然后给你m个箱子，长和宽都告诉你，把箱子靠左放，求箱子的底部有多高。

   因为都是放在最左边的，所以只要和最左边的高度比较，这样就不用更新线段树了。

代码：

  

   

    

     

    
    

     

      //cf 272 C
     
    
   

    

     

    
    

     

      //2013-05-14-20.26
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int maxn = 100005;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int l, r, mid;
     
    
   

    

     

    
    

     

          __int64 m;
     
    
   

    

     

    
    

     

      }tree[maxn<<2];
     
    
   

    

     

    
    

     

      __int64 a[maxn];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      __int64 max(__int64 a, __int64 b)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    if (a > b)
     
    
   

    

     

    
    

     
        return a;
     
    
   

    

     

    
    

     
    return b;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void build(int l, int r, int o)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          tree[o].l = l;
     
    
   

    

     

    
    

     

          tree[o].r = r;
     
    
   

    

     

    
    

     
    int mid = (l+r)>>1;
     
    
   

    

     

    
    

     

          tree[o].mid = mid;
     
    
   

    

     

    
    

     
    if (l == r)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              tree[o].m = a[l];
     
    
   

    

     

    
    

     
        return ;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    build(l, mid, o<<1);
     
    
   

    

     

    
    

     
    build(mid+1, r, (o<<1)+1);
     
    
   

    

     

    
    

     

          tree[o].m = max(tree[o<<1].m, tree[(o<<1)+1].m);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int query(int l, int r, int o)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    if (l == tree[o].l && tree[o].r == r)
     
    
   

    

     

    
    

     
        return tree[o].m;
     
    
   

    

     

    
    

     
    if (r <= tree[o].mid)
     
    
   

    

     

    
    

     
        return query(l, r, o<<1);
     
    
   

    

     

    
    

     
    else if (l > tree[o].mid)
     
    
   

    

     

    
    

     
        return query(l, r, (o<<1)+1);
     
    
   

    

     

    
    

     
    else
     
    
   

    

     

    
    

     
        return max(query(l, tree[o].mid, o<<1), query(tree[o].mid+1, r, (o<<1)+1));
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int n, m;
     
    
   

    

     

    
    

     
    while (scanf("%d", &n) != EOF)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        for (int i = 1; i <= n; i++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            scanf("%I64d", &a[i]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        build(1, n, 1);
     
    
   

    

     

    
    

     

              __int64 high = a[1];
     
    
   

    

     

    
    

     
        scanf("%d", &m);
     
    
   

    

     

    
    

     

              __int64 w, h;
     
    
   

    

     

    
    

     
        while (m--)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            scanf("%I64d %I64d", &w, &h);
     
    
   

    

     

    
    

     
            printf("%I64d\n", max(query(1, w, 1), high));
     
    
   

    

     

    
    

     

                  high = max(query(1, w, 1), high) + h;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/8927545