1400 -

1400 - "Ray, Pass me the dishes!"
第一次做线段树题目，确实一点也不会，想了很久，首先是线段树怎么作用，每一步会产生什么影响。
首先，线段树的每次更新都更新了什么，为什么要这么更新，尤其是更新的区间，虽说原理很简单，就是要么在左子树，
要么在右子树，要么兼顾左右子树，所以如果是在左子树，那就查找左子树，否则右子树，或者左右子树都查找，再合并左右子树，
这仅是对于查找而言的。那么建树是怎么回事呢，首先建树必然会包括所有情况，每种情况事实上的是在这个过程中不断更新，
事实上就是符合每次区间[l, r]的查找罢了，就是特殊情况处理了，然后再从特殊情况中拼凑出非特殊情况就可以了
#include <iostream>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>

#define INF 0x7ffffffffffLL
#define N 500010
#define LL long long
#define mod 95041567

using namespace std;

struct node{
    LL MAX, MAX_PREFIX, MAX_SUFFIX;
    int l, r, ll, rr;
};

LL sum[N];
node G[N << 2];

void pushup(int L, int R, int rt){
    int mid = (R - L) / 2 + L;

    G[rt].MAX_PREFIX = G[rt << 1].MAX_PREFIX, G[rt].ll = G[rt << 1].ll;
    if(G[rt].MAX_PREFIX < G[(rt << 1) | 1].MAX_PREFIX + sum[mid] - sum[L - 1]){
        G[rt].MAX_PREFIX = G[(rt << 1) | 1].MAX_PREFIX + sum[mid] - sum[L - 1];
        G[rt].ll = G[(rt << 1) | 1].ll;
    }

    G[rt].MAX_SUFFIX = G[(rt << 1) | 1].MAX_SUFFIX, G[rt].rr = G[(rt << 1) | 1].rr;
    if(G[rt].MAX_SUFFIX <= G[rt << 1].MAX_SUFFIX + sum[R] - sum[mid]){
        G[rt].MAX_SUFFIX = G[rt << 1].MAX_SUFFIX + sum[R] - sum[mid];
        G[rt].rr = G[rt << 1].rr;
    }

    G[rt].MAX = G[rt << 1].MAX, G[rt].l = G[rt << 1].l, G[rt].r = G[rt << 1].r;
    if(G[(rt << 1) | 1].MAX > G[rt].MAX){
        G[rt].MAX = G[(rt << 1) | 1].MAX; 
        G[rt].l = G[(rt << 1) | 1].l; 
        G[rt].r = G[(rt << 1) | 1].r;
    }
    if(G[rt].MAX < G[rt << 1].MAX_SUFFIX + G[(rt << 1) | 1].MAX_PREFIX){
        G[rt].MAX = G[rt << 1].MAX_SUFFIX + G[(rt << 1) | 1].MAX_PREFIX;
        G[rt].l = G[rt << 1].rr;
        G[rt].r = G[(rt << 1) | 1].ll;
    }
    else if(G[rt].MAX == G[rt << 1].MAX_SUFFIX + G[(rt << 1) | 1].MAX_PREFIX){
        if(G[rt].l > G[rt << 1].rr){
            G[rt].l = G[rt << 1].rr;
            G[rt].r = G[(rt << 1) | 1].ll;
        }
        else if(G[rt].l == G[rt << 1].rr && G[rt].r > G[(rt << 1) | 1].ll)
            G[rt].r = G[(rt << 1) | 1].ll;
    }
}

void build_tree(int L, int R, int rt){
    if(L == R){
        G[rt].l = G[rt].r = L;
        G[rt].ll = G[rt].rr = L;
        G[rt].MAX = G[rt].MAX_SUFFIX = G[rt].MAX_PREFIX = sum[L] - sum[L - 1];
        return;
    }
    int mid = (R - L) / 2 + L;
    build_tree(L, mid, rt << 1);
    build_tree(mid + 1, R, (rt << 1) | 1);
    pushup(L, R, rt);
}

node query(int L, int R, int rt, int l, int r){
    if(L == l && R == r) return G[rt];
    int mid = (R - L) / 2 + L;
    if(mid < l) return query(mid + 1, R, (rt << 1) | 1, l, r);
    if(r <= mid) return query(L, mid, rt << 1, l, r);

    node ln = query(L, mid, rt << 1, l, mid);
    node rn = query(mid + 1, R, (rt << 1) | 1, mid + 1, r);
    node v = ln;
    if(v.MAX < rn.MAX) v = rn;
    if(v.MAX < ln.MAX_SUFFIX + rn.MAX_PREFIX){
        v.MAX = ln.MAX_SUFFIX + rn.MAX_PREFIX;
        v.l = ln.rr;
        v.r = rn.ll;
    }
    else if(v.MAX == ln.MAX_SUFFIX + rn.MAX_PREFIX){
        if(v.l > ln.rr){
            v.l = ln.rr;
            v.r = rn.ll;
        }
        else if(v.l == ln.rr && v.r > rn.ll) v.r = rn.ll;
    }

    v.MAX_PREFIX = ln.MAX_PREFIX, v.ll = ln.ll;
    v.MAX_SUFFIX = rn.MAX_SUFFIX, v.rr = rn.rr;

    if(v.MAX_PREFIX < sum[mid] - sum[l - 1] + rn.MAX_PREFIX){
        v.MAX_PREFIX = sum[mid] - sum[l - 1] + rn.MAX_PREFIX;
        v.ll = rn.ll;
    }

    if(v.MAX_SUFFIX <= sum[r] - sum[mid] + ln.MAX_SUFFIX){
        v.MAX_SUFFIX = sum[r] - sum[mid] + ln.MAX_SUFFIX;
        v.rr = ln.rr;
    }

    return v;
}
int main()
{
  //  freopen("in.txt","r",stdin);
    int m, n, t = 1;
    sum[0] = 0;
    while(scanf("%d %d", &n, &m) != EOF){
        for(int i = 1; i <= n; ++i){
            scanf("%lld", &sum[i]);
            sum[i] += sum[i - 1];
        }
        build_tree(1, n, 1);
        printf("Case %d:\n", t++);
        int l, r;
        for(int i = 0; i < m; ++i){
            scanf("%d %d", &l, &r);
            node v = query(1, n, 1, l, r);
            printf("%d %d\n", v.l, v.r);
        }
    }
    return 0;
}
1400 - "Ray, Pass me the dishes!"

相关推荐
