题目很长，看加猜加谷歌翻译才看懂了题目。每级台阶的宽都是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; }
