记录编号	561771	评测结果	EEEEEEEEEE
题目名称	Can you answer these queries III	最终得分	0
用户昵称	yrtiop	是否通过	未通过
代码语言	C++	运行时间	1.290 s
提交时间	2021-07-03 14:21:49	内存使用	50.96 MiB

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 6;
int n, m, a[MAXN];

struct node {
    int l, r, sum, dat, lda, rda;
}tree[MAXN << 2];

void pushup (int i) {
    tree[i].lda = max (tree[i << 1].sum + tree[i << 1 | 1].lda, tree[i << 1].lda);
    tree[i].rda = max (tree[i << 1 | 1].sum + tree[i << 1].rda, tree[i << 1 | 1].rda);
    tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
    tree[i].dat = max (max (tree[i << 1].dat, tree[i << 1 | 1].dat), tree[i << 1].rda + tree[i << 1 | 1].lda);
    return ; 
}

void build (int i, int l, int r) {
    if (l == r) {
        tree[i].sum = tree[i].lda = tree[i].rda = tree[i].dat = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build (i << 1, l, mid) ;
    build (i << 1 | 1, mid + 1, r);
    pushup (i);
    return ;
}
        
void update (int i, int d, int k) {
    if (tree[i].l == tree[i].r) {
        tree[i].sum = tree[i].lda = tree[i].rda = tree[i].dat = k;
        return ;
    }
    if (tree[i << 1].r >= d) {
        update (i << 1 , d, k);
    } 
    else update (i << 1 | 1 , d, k);
    pushup (i);
    return ;
}

node query (int i, int l, int r) {
    if (tree[i].l >= l && tree[i].r <= r) {
        return tree[i];
    }
    int mid = tree[i].l + tree[i].r >> 1;
    if (r <= mid) return query (i << 1, l, r);
    if (l > mid) return query (i << 1 | 1, l, r);
    int s = -1e8;
    node a, b, c;
    a = query (i << 1, l ,r);
    b = query (i << 1 | 1, l ,r);
    c.sum = a.sum + b.sum;
    c.lda = max (a.lda, a.sum + b.lda);
    c.rda = max (b.rda, b.sum + a.rda);
    c.dat = max (max (a.dat, b.dat), a.rda + b.lda) ;
    return c;
}

int main () {
    freopen ("GSS_3.in", "r", stdin);
    freopen ("GSS_3.out", "w", stdout);
    scanf ("%d %d", &n ,&m);
    for (int q = 1; q <= n; ++q) {
        scanf ("%d", &a[q]);
    }
    build (1, 1, n);
    for (int q = 1, x, y, k; q <= m; ++q) {
        scanf ("%d %d %d", &k, &x, &y);
        if (k & 1) {
            if (x > y) swap (x, y);
            node d = query (1, x, y);
            printf ("%d\n", d.dat);
        }
        else {
            update (1, x, y);
        }
    }
    return 0;
}