最大子段和SP1716GSS3 线段树

前言

spoj需要FQ注册，比较麻烦，大家就在luogu评测吧

题目大意:

$n$ 个数，$q$ 次操作

操作$0 _ x_ y$把$A_x$ 修改为$y$

操作$1 _ l _r$询问区间$[l, r]$ 的最大子段和

思路

维护一个区间的$sum,lmax,rmax,max$

就是区间和，左端开头的最大字段和，右端开头的最大字段和和区间内的最大字段和

他们都说转移难，我咋感觉是询问难呢

转移的话

①max 就是右边，左边，和交界处的最大值，取个max

②lmax和rmax类似，就是有两种可能，一种是只在一个孩子内，一种是两个孩子内(完全包含一个孩子)

③sum不必说(其实就是为了求lmax和rmax的)

查询的话，当然不能加起来啦，如果不连续不就GG了

①如果全部在一个孩子内，直接去查询那个孩子就好

②如果横跨两个孩子的话，还要讨论一下交界处

看着很明白，也许是我太菜了不太会递归吧

我居然能忘记维护sum，也是醉了

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bitset>
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int maxn = 50007;
const int maxm = 250007;
const int inf = 0x3f3f3f3f;

int n, m, a[maxn],tot[maxn];
struct node {
    int l, r;
    int lk, rk, k, sum;
} e[maxm];

int read() {
    int x = 0, f = 1; char s = getchar();
    for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;
    for (; s <= '9' && s >= '0'; s = getchar()) x = x * 10 + s - '0';
    return x * f;
}

int max_2(int a, int b, int c) {
    return max(max(a, b), c);
}

void pushup(int rt) {
    e[rt].k = max_2(e[ls].k, e[rs].k, e[ls].rk + e[rs].lk);
    e[rt].lk = max(e[ls].sum + e[rs].lk, e[ls].lk);
    e[rt].rk = max(e[ls].rk + e[rs].sum, e[rs].rk);
    e[rt].sum= e[ls].sum +e[rs].sum;
}

void build(int l, int r, int rt) {
    e[rt].l = l, e[rt].r = r, e[rt].sum = tot[r] - tot[l-1];
    if (l == r) {
        e[rt].k = e[rt].lk = e[rt].rk = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    pushup(rt);
}

void update(int L, int k, int rt) {
    if (e[rt].l == e[rt].r) {
        e[rt].sum=k;
        e[rt].k = e[rt].lk = e[rt].rk = k;
        return;
    }
    int mid = (e[rt].l + e[rt].r) >> 1;
    if (L <= mid) update(L, k, ls);
    else update(L, k, rs);
    pushup(rt);
}
void debug() {
    printf("debug\n");
    printf("               %d\n", e[1].k);
    printf("       %d               %d\n", e[2].k, e[3].k );
    printf("   %d       %d       %d       %d\n", e[4].k, e[5].k, e[6].k, e[7].k );
}

node query(int L, int R, int rt) {
    if(L<=e[rt].l&&e[rt].r<=R) {
        return e[rt];
    }
    int mid = (e[rt].l + e[rt].r) >> 1;
    if(L <= mid && R > mid) {
        node x=query(L, R, ls),y=query(L, R, rs);
        node tmp={};

        tmp.k = max_2(x.k, y.k, x.rk + y.lk);
        tmp.lk =max(x.sum + y.lk, x.lk);
        tmp.rk =max(x.rk + y.sum, y.rk);
        return tmp;
    }
    if (L <= mid) return query(L, R, ls);
    if (R > mid) return query(L, R, rs);
}

int main() {
    //freopen("in.txt","r",stdin);
    n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        tot[i]=tot[i-1]+a[i];
    }
    build(1, n, 1);
    m = read();
    for (; m--;) {
        int tmp = read(), a = read(), b = read();
        if (tmp) {
            printf("%d\n",max_2(query(a, b, 1).k,query(a,b,1).lk,query(a,b,1).rk) );
        } else {
            update(a, b, 1);
        }
    }
    //debug();
    return 0;
}