学步园

线段树的应用

每个结点维护3个值，最大连续和max_sub，最大前缀和max_prefix与最大后缀和max_suffix.

思想：最有解要么在左边，要么在右边，要么跨越中点。

维护max_sub的同时维护max_prefix,max_suffix即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

const ll INF = -(1LL<<60);
const int MAXN = 500007;
struct node {
    int l, r;
    ll n;
    bool operator < (const node & no) const {
        return n<no.n || n==no.n&&l>no.l || n==no.n&&l==no.l&&r>no.r;
    }
}maxv[MAXN << 2];
int maxl[MAXN << 2], maxr[MAXN << 2];
ll x[MAXN], sum[MAXN];

void build(int num, int l, int r) {
    if(l == r) {
        maxv[num] = node{l, r, x[l]};
        maxl[num] = maxr[num] = l;
        return ;
    }
    int m = (l + r) >> 1;
    build(num<<1, l, m);
    build(num<<1|1, m+1, r);

    maxv[num] = node{l, r, INF};
    maxv[num] = max(maxv[num], maxv[num<<1]);
    maxv[num] = max(maxv[num], maxv[num<<1|1]);
    maxv[num] = max(maxv[num], node{maxr[num<<1], maxl[num<<1|1], sum[maxl[num<<1|1]] - sum[maxr[num<<1] - 1]});

    maxl[num] = maxl[num<<1];
    if(sum[maxl[num]] - sum[l - 1] < sum[maxl[num<<1|1]] - sum[l-1]) maxl[num] = maxl[num<<1|1];

    maxr[num] = maxr[num<<1|1];
    if(sum[r] - sum[maxr[num] - 1] <= sum[r] - sum[maxr[num<<1] - 1]) maxr[num] = maxr[num<<1];
}

node getans(int num, int l, int r, int a, int b, int &tmaxl, int &tmaxr) {
    if(a <= l && b >= r) {
        tmaxl = maxl[num];
        tmaxr = maxr[num];
        return maxv[num];
    }
    int m = (l+r)>>1;
    node ans = node{l, r, INF};
    int lmaxr, lmaxl, rmaxl, rmaxr;
    tmaxl = tmaxr = -1;
    if(a <= m && b > m) {
        ans  = max(ans, getans(num<<1, l, m, a, b, lmaxl, lmaxr));
        ans = max(ans, getans(num<<1|1, m+1, r, a, b, rmaxl, rmaxr));
        if(rmaxl != -1 && lmaxr != -1)
            ans = max(ans, node{lmaxr, rmaxl, sum[rmaxl] - sum[lmaxr-1]});
        if(a <= l) {
            tmaxl = lmaxl;
            if(sum[lmaxl] - sum[l-1] < sum[rmaxl] - sum[l-1]) tmaxl = rmaxl;
        }
        if(b >= r) {
            tmaxr = rmaxr;
            if(sum[r] - sum[rmaxr-1] <= sum[r] - sum[lmaxr-1]) tmaxr = lmaxr;
        }
    }
    else if(a <= m) {
        ans  = max(ans, getans(num<<1, l, m, a, b, lmaxl, lmaxr));
        if(a <= l) tmaxl = lmaxl;
    }
    else if(b > m) {
        ans = max(ans,getans(num<<1|1, m+1, r, a, b, rmaxl, rmaxr));
        if(b >= r) tmaxr = rmaxr;
    }
    return ans;
}

int main() {
    int n, m, id = 0;
    while(~scanf("%d%d", &n, &m)) {
        memset(sum, 0, sizeof(sum));
        int i;
        for(i = 1; i <= n; i++) {
            scanf("%lld", x + i);
            sum[i] = sum[i - 1] + x[i];
        }
        build(1,1,n);
        printf("Case %d:\n", ++id);
        while(m --) {
            int l, r, a, b;
            scanf("%d%d", &a, &b);
            node ans = getans(1, 1, n, a, b, l, r);
            printf("%d %d\n", ans.l, ans.r);
        }
    }
    return 0;
}