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