学步园

题意：给定一个长度为n的序列，每次询问一个区间[a, b]，求出该区间内最大连续和的范围。

维护线段树节点的5个域：l, r区间的左右端点；x, y最大连续和的范围的左右端点；ln最大前缀和的右端点；rn最大后缀和的左端点。在区间合并的时候，分情况讨论，不详述。

查询的时候，如果待查询区间“横跨”了所在区间的中点，分三种情况讨论：最大连续和在左区间，在右区间，以及跨区间中点。对于跨区间中点的情况，要应用另外一种查询方式，即查询在范围内的最大前缀和以及最大后缀和。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lng long long
#define lson(x) (x << 1)
#define rson(x) (x << 1) | 1
using namespace std;

const int maxn = 500000 + 10;
struct node
{
    int l, r;
    int x, y;
    int ln, rn;
}tree[maxn];
int n, m;
lng sum[maxn];

void pushup(int now)
{
    lng tmp = sum[tree[rson(now)].ln] - sum[tree[lson(now)].rn - 1];
    tree[now].x = tree[lson(now)].rn; tree[now].y = tree[rson(now)].ln;
    lng ltmp = sum[tree[lson(now)].y] - sum[tree[lson(now)].x - 1];
    if(ltmp >= tmp) { tmp = ltmp; tree[now].x = tree[lson(now)].x; tree[now].y = tree[lson(now)].y; }
    lng rtmp = sum[tree[rson(now)].y] - sum[tree[rson(now)].x - 1];
    if(rtmp > tmp) { tmp = rtmp; tree[now].x = tree[rson(now)].x; tree[now].y = tree[rson(now)].y; }
    tree[now].ln = tree[lson(now)].ln;
    lng a = sum[tree[now].ln] - sum[tree[now].l - 1], b = sum[tree[rson(now)].ln] - sum[tree[now].l - 1];
    if(b > a) tree[now].ln = tree[rson(now)].ln;
    tree[now].rn = tree[rson(now)].rn;
    a = sum[tree[now].r] - sum[tree[now].rn - 1]; b = sum[tree[now].r] - sum[tree[lson(now)].rn - 1];
    if(b >= a) tree[now].rn = tree[lson(now)].rn;
}

void build(int l, int r, int now)
{
    tree[now].l = l; tree[now].r = r;
    if(l == r) { tree[now].x = l; tree[now].y = r; tree[now].ln = r; tree[now].rn = l; }
    else
    {
        int mid = (l + r) >> 1;
        build(l, mid, lson(now));
        build(mid + 1, r, rson(now));
        pushup(now);
    }
    //printf("%d %d %d %d %d %d\n", l, r, tree[now].x, tree[now].y, tree[now].ln, tree[now].rn);
}

int queryl(int x, int now)
{
    if(x >= tree[now].ln) return tree[now].ln;
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(x <= mid) { return queryl(x, lson(now)); }
    else
    {
        int tmp = queryl(x, rson(now));
        lng a = sum[tmp] - sum[tree[now].l - 1], b = sum[tree[lson(now)].ln] - sum[tree[now].l - 1];
        if(a > b) return tmp;
        else return tree[lson(now)].ln;
    }
}

int queryr(int x, int now)
{
    if(x <= tree[now].rn) return tree[now].rn;
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(x > mid) { return queryr(x, rson(now)); }
    else
    {
        int tmp = queryr(x, lson(now));
        lng a = sum[tree[now].r] - sum[tmp - 1], b = sum[tree[now].r] - sum[tree[rson(now)].rn - 1];
        if(a >= b) return tmp;
        else return tree[rson(now)].rn;
    }
}

void query(int l, int r, int now, int & x, int & y)
{
    if(l <= tree[now].l && r >= tree[now].r) { x = tree[now].x; y = tree[now].y; return;}
    else
    {
        int mid = (tree[now].l + tree[now].r) >> 1;
        if(r <= mid) { query(l, r, lson(now), x, y); }
        else if(l > mid) { query(l, r, rson(now), x, y); }
        else
        {
            int tmpx = queryr(l, lson(now)), tmpy = queryl(r, rson(now));
            lng tmp = sum[tmpy] - sum[tmpx - 1];
            query(l, mid, lson(now), x, y);
            lng ltmp = sum[y] - sum[x - 1];
            if(ltmp >= tmp) { tmpx = x; tmpy = y; tmp = ltmp; }
            query(mid + 1, r, rson(now), x, y);
            lng rtmp = sum[y] - sum[x - 1];
            if(rtmp > tmp) { tmpx = x; tmpy = y; tmp = rtmp; }
            x = tmpx; y = tmpy;
        }
    }
}

int main()
{
    freopen("in", "r", stdin);
    int cc = 1;
    while(~scanf("%d %d", &n, &m))
    {
        sum[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            int a; scanf("%d", &a);
            sum[i] = sum[i - 1] + a;
        }
        build(1, n, 1);
        printf("Case %d:\n", cc++);
        while(m--)
        {
            int a, b, x, y; scanf("%d %d", &a, &b);
            query(a, b, 1, x, y);
            printf("%d %d\n", x, y);
        }
    }
    return 0;
}

/*
3 1 
1 2 3 
1 1

Case 1: 
1 1
*/