学步园

线段树，后面下标处理有点乱，有空再修改;

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAXN 500010
#define INF (~0U >> 2)
using std::max;
using std::cout;
using std::endl;
typedef long long LL;
#define Lson l, mid, rt << 1
#define Rson mid + 1, r, rt << 1 | 1
LL A[MAXN], sum[MAXN << 2], max_sub[MAXN << 2], max_prefix[MAXN << 2], max_suffix[MAXN << 2];
int max_sub_x[MAXN << 2], max_sub_y[MAXN << 2], max_prefix_x[MAXN << 2], max_prefix_y[MAXN << 2], max_suffix_x[MAXN << 2], max_suffix_y[MAXN << 2];
void sum_push_up(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void prefix_push_up(int rt){
	max_prefix[rt] = max(max_prefix[rt << 1], sum[rt << 1] + max_prefix[rt << 1 | 1]);
	if (max_prefix[rt << 1] >= sum[rt << 1] + max_prefix[rt << 1 | 1]) {
		max_prefix_x[rt] = max_prefix_x[rt << 1]; max_prefix_y[rt] = max_prefix_y[rt << 1];
	}
	else {
		max_prefix_x[rt] = max_prefix_x[rt << 1]; max_prefix_y[rt] = max_prefix_y[rt << 1 | 1];
	}
}
void suffix_push_up(int rt){
	max_suffix[rt] = max(max_suffix[rt << 1 | 1], max_suffix[rt << 1] + sum[rt << 1 | 1]);
	if (max_suffix[rt << 1 | 1] > max_suffix[rt << 1] + sum[rt << 1 | 1]) {
		max_suffix_x[rt] = max_suffix_x[rt << 1 | 1]; max_suffix_y[rt] = max_suffix_y[rt << 1 | 1];
	}
	else {
		max_suffix_x[rt] = max_suffix_x[rt << 1]; max_suffix_y[rt] = max_suffix_y[rt << 1 | 1];
	}
}
void sub_push_up(int rt) {
	max_sub[rt] = max(max(max_sub[rt << 1], max_sub[rt << 1 | 1]), max_suffix[rt << 1] + max_prefix[rt << 1 | 1]);
	if (max_sub[rt << 1] >= max_sub[rt << 1 | 1] && max_sub[rt << 1] >= max_suffix[rt << 1] + max_prefix[rt << 1 | 1]) {
		max_sub_x[rt] = max_sub_x[rt << 1]; max_sub_y[rt] = max_sub_y[rt << 1];
	}
	else if (max_sub[rt << 1 | 1] > max_suffix[rt << 1] + max_prefix[rt << 1 | 1]) {
		max_sub_x[rt] = max_sub_x[rt << 1 | 1]; max_sub_y[rt] = max_sub_y[rt << 1 | 1];
	}
	else {
		max_sub_x[rt] = max_suffix_x[rt << 1]; max_sub_y[rt] = max_prefix_y[rt << 1 | 1];
	}
}
void push_up(int rt){
    sum_push_up(rt);
    suffix_push_up(rt);
    prefix_push_up(rt);
    sub_push_up(rt);
}
void build(int l, int r, int rt) {
    if (l == r) {
        sum[rt] = A[l];
        max_sub[rt] = A[l];
        max_prefix[rt] = A[l];
        max_suffix[rt] = A[l];
        max_sub_x[rt] = l; max_sub_y[rt] = r;
        max_prefix_x[rt] = l; max_prefix_y[rt] = r;
        max_suffix_x[rt] = l; max_suffix_y[rt] = r;
        return;
    }
    int mid = (l + r) >> 1;
    build(Lson);
    build(Rson);
    push_up(rt);
}
int query1(int L, int R, int l, int r, int rt, int &x, int &y) {
    if (L <= l && r <= R) {
    	x = max_sub_x[rt]; y = max_sub_y[rt];
    	return rt;
    }
    int mid = (l + r) >> 1;
    LL ret1, ret2;
    int r1 = 0, r2 = 0;
    ret1 = ret2 = -1000000001LL;
    if (L <= mid)
        r1 = query1(L, R, Lson, x, y);
    if (R > mid)
        r2 = query1(L, R, Rson, x, y);
	if (r1) ret1 = max_sub[r1];
	if (r2) ret2 = max_sub[r2];
	if (ret1 > ret2){
		x = max_sub_x[r1]; y = max_sub_y[r1];
		return r1;
	}
	else {
		x = max_sub_x[r2]; y = max_sub_y[r2];
		return r2;
	}
}
LL query2(int L, int R, int l, int r, int rt, int &x, int &y) {
	//puts("ok");
	if (L <= l && r <= R) {
		if (L == l && r == R){
			x = max_sub_x[rt]; y = max_sub_y[rt];
			return max_sub[rt];
		}
		else if (l == L) {
			x = max_suffix_x[rt];
			return max_suffix[rt];
		}
		else if (r == R) {
			y = max_prefix_y[rt];
			return max_prefix[rt];
		}
		else {
			return sum[rt];
		}
	}
	int ret = 0;
	int mid = (l + r) >> 1;
	if (L <= mid)
        ret += query2(L, R, Lson, x, y);
    if (R > mid)
        ret += query2(L, R, Rson, x, y);
	return ret;
}
int main()
{
	int n, m, now = 0;
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 1; i <= n; ++ i) scanf("%lld", &A[i]);
		build(1, n, 1);
		//for (int i = 1; i <= 2 * n; ++ i) printf ("%lld ", sum[i]); puts("");
		//for (int i = 1; i <= 2 * n; ++ i) printf ("%lld ", max_sub[i]); puts("");
		//for (int i = 1; i <= 2 * n; ++ i) printf ("%d ", max_prefix_x[i]); puts("");
		//for (int i = 1; i <= 2 * n; ++ i) printf ("%d ", max_prefix_y[i]); puts("");
		//for (int i = 1; i <= 2 * n; ++ i) printf ("%d ", max_suffix_x[i]); puts("");
		//for (int i = 1; i <= 2 * n; ++ i) printf ("%d ", max_suffix_y[i]); puts("");
		printf("Case %d:\n", ++ now);
		for (int i = 0; i < m; ++ i) {
			int a, b, x1, y1, x2, y2;
			scanf("%d%d", &a, &b);
			int rt = query1(a, b, 1, n ,1, x1, y1);
			//cout << rt << endl;
			LL ret1 = max_sub[rt], ret2 = query2(a, b, 1, n, 1, x2, y2);
			//cout << x1 << "," << y1 << " " << x2 << "," << y2 << endl;
			//cout << max_sub_x[2] << "," << max_sub_y[2] <<endl;
			//printf("%lld %lld\n", query1(a, b, 1, n ,1), query2(a, b, 1, n, 1));
			//printf("%lld %lld\n", ret1, ret2);
			if (ret1 > ret2) {
				printf("%d %d\n", x1, y1);
			}
			else if (ret1 < ret2) {
				printf("%d %d\n", x2, y2);
			}
			else {
				if (x1 < x2) {
					printf ("%d %d\n", x1, y1);
				}
				else if (x1 == x2) {
					if (y1 < y2) printf ("%d %d\n", x1, y1);
					else printf ("%d %d\n", x2, y2);
				}
				else
					printf ("%d %d\n", x2, y2);
			}
		}
	}
}