题意： 给你一个序列 （n <= 500000）， 求其动态最大子段和的左右两端下标（x，y），询问（q <= 500000）， 注意一定要取一个数，如果最大和相等 取x最小的那段，又如果x相等，取y最小的那段。
如果只求和，那么这题还算比较顺手， 但求下标，节点保存的数据比较多，导致更新的时候很容易出错，其实题目本身还是很容易想到的，只是比较麻烦，锻炼查错能力。
思路；
对于某一区间最值的更新：
1. 左区间的最值
2 右区间的最值
3 左区间的最大后缀和 + 右区间的最大前缀和
对于最大前缀和的更新：
１ 左区间的最大前缀和
２ 左区间的和 + 右区间的最大前缀和
对于最大后缀和的更新： 类似前缀
下标在更新最值，最大前缀，最大后缀 时 一同更新。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 500005
#define lc rt<<1
#define rc rt<<1|1
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mid int m = (l + r) >> 1
#define LL long long
int n;
struct node {
LL sum, max, lsum, rsum; // 区间和，最大值，最大前缀和，最大后缀和
int l, r, ll, rr; // 最大区间左右端点， 最大前缀和端点， 最大后缀和端点
}a[maxn<<2];
void pushup(int l, int r, int rt) {
mid;
a[rt].sum = a[lc].sum + a[rc].sum; // sum
a[rt].lsum = a[lc].lsum; a[rt].rsum = a[rc].rsum; //lsum, rsum
a[rt].ll = a[lc].ll; a[rt].rr = a[rc].rr;
if(a[lc].sum + a[rc].lsum > a[rt].lsum )
a[rt].lsum = a[lc].sum + a[rc].lsum, a[rt].ll = a[rc].ll;
if(a[rc].sum + a[lc].rsum >= a[rt].rsum )
a[rt].rsum = a[rc].sum + a[lc].rsum, a[rt].rr = a[lc].rr;
int tp; // max, l, r
if(a[lc].max >= a[rc].max) tp = lc;
else tp = rc;
a[rt].max = a[tp].max; a[rt].l = a[tp].l; a[rt].r = a[tp].r;
LL tt = a[lc].rsum + a[rc].lsum;
if(tt > a[rt].max || tt == a[rt].max && a[rt].l > a[lc].rr
|| tt == a[rt].max && a[rt].l == a[lc].rr && a[rt].r > a[rc].ll)
a[rt].max = tt, a[rt].l = a[lc].rr, a[rt].r = a[rc].ll;
}
void build(int l=1, int r=n, int rt=1) {
if(l == r) {
scanf("%lld", &a[rt].sum);
a[rt].max = a[rt].lsum = a[rt].rsum = a[rt].sum;
a[rt].l = a[rt].r = a[rt].ll = a[rt].rr = l;
return;
}
mid;
build(lson);
build(rson);
pushup(l, r, rt);
/*
printf("l = %d r = %d\n", l, r);
printf("max = %lld sum = %lld lsum = %lld rsum = %lld\n", a[rt].max, a[rt].sum, a[rt].lsum, a[rt].rsum);
printf("~~~~~~l = %d r = %d ll = %d rr = %d\n", a[rt].l, a[rt].r, a[rt].ll, a[rt].rr);
*/
}
node query(int L, int R, int l=1, int r=n, int rt=1) {
if(L == l && r == R)
return a[rt];
mid;
if(L > m) return query(L, R, rson);
else if(R <= m) return query(L, R, lson);
else {
node t1 = query(L, m, lson);
node t2 = query(m+1, R, rson);
/*
printf("query: l = %d r = %d m = %d\n", l, r, m);
printf("max = %lld sum = %lld lsum = %lld rsum = %lld\n", t1.max, t1.sum, t1.lsum, t1.rsum);
printf("!!!!l = %d r = %d ll = %d rr = %d\n", t1.l, t1.r, t1.ll, t1.rr);
puts("");
printf("max = %lld sum = %lld lsum = %lld rsum = %lld\n", t2.max, t2.sum, t2.lsum, t2.rsum);
printf("!!!!l = %d r = %d ll = %d rr = %d\n", t2.l, t2.r, t2.ll, t2.rr);
*/
node ret;
ret.sum = t1.sum + t2.sum; // sum
if(t1.max >= t2.max) ret = t1; // max
else ret = t2;
LL tt = t1.rsum + t2.lsum;
if(tt > ret.max || tt == ret.max && t1.rr < ret.l
|| tt == ret.max && t1.rr == ret.l && t2.ll < ret.r)
ret.max = tt, ret.l = t1.rr, ret.r = t2.ll;
ret.lsum = t1.lsum; ret.rsum = t2.rsum; // lsum, rsum
ret.ll = t1.ll; ret.rr = t2.rr;
if(t1.sum + t2.lsum > ret.lsum )
ret.lsum = t1.sum + t2.lsum, ret.ll = t2.ll;
if(t2.sum + t1.rsum >= ret.rsum )
ret.rsum = t2.sum + t1.rsum, ret.rr = t1.rr;
return ret;
}
}
int main() {
int i, j, cas = 1, m;
while( ~scanf("%d%d", &n, &m)) {
build();
printf("Case %d:\n", cas++);
int x, y;
while(m--) {
scanf("%d%d", &x, &y);
node t = query(x, y);
printf("%d %d\n", t.l, t.r);
}
}
return 0;
}
/*
8 100
-2 3 4 -6 6 10 -7 100
*/