ker_xyxyxyx_xxs @ 2021-07-14 11:45:47
```cpp
# include <iostream>
# include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
int w[maxn];
int n , m , opt , x , y;
typedef struct {
int l , r;
int maxl , maxr , maxp , val;
} seg;
seg tr[maxn * 4];
int max1(int , int);
int max2(int , int , int);
void update(int);
int getl(int , int , int);
int getr(int , int , int);
void build(int , int , int);
void modify(int , int , int);
int query(int , int , int);
int main() {
scanf("%d%d" , &n , &m);
for (int i = 1 ; i <= n ; i ++) {
scanf("%d" , &w[i]);
}
build(1 , 1 , n);
for (int i = 1 ; i <= m ; i ++) {
scanf("%d%d%d" , &opt , &x , &y);
if (opt == 1) {
if (x > y) swap(x , y);
printf("%d\n" , query(1 , x , y));
} else {
modify(1 , x , y);
}
}
return 0;
}
int max1(int a , int b) {
return a > b ? a : b;
}
int max2(int a , int b , int c) {
return max1(a , max1(b , c));
}
void update(int p) {
int ls = p << 1;
int rs = p << 1 | 1;
tr[p].val = tr[ls].val + tr[rs].val;
tr[p].maxl = max1(tr[ls].maxl , tr[ls].val + tr[rs].maxl);
tr[p].maxr = max1(tr[rs].maxr , tr[rs].val + tr[ls].maxr);
tr[p].maxp = max2(tr[ls].maxp , tr[rs].maxp , tr[ls].maxr + tr[rs].maxl);
}
int getl(int p , int l , int r) {
int ls = p << 1;
int rs = p << 1 | 1;
if (tr[p].r <= r) return tr[p].maxl;
int mid = (tr[p].l + tr[p].r) >> 1;
if (r < mid) return getl(ls , l , r);
else {
int tot = tr[ls].val + getl(rs , l , r);
return max1(tr[ls].maxl , tot);
}
}
int getr(int p , int l , int r) {
int ls = p << 1;
int rs = p << 1 | 1;
if (l <= tr[p].l) return tr[p].maxr;
int mid = (tr[p].l + tr[p].r) >> 1;
if (l > mid) return getr(rs , l , r);
else {
int tot = tr[rs].val + getr(ls , l , r);
return max1(tr[ls].maxr , tot);
}
}
void build(int p , int l , int r) {
tr[p].l = l;
tr[p].r = r;
if (l == r) {
tr[p].val = w[l];
tr[p].maxl = tr[p].maxp = tr[p].maxr = tr[p].val;
return ;
} else {
int mid = (l + r) >> 1;
build(p << 1 , l , mid);
build(p << 1 , mid + 1 , r);
update(p);
}
}
void modify(int p , int x , int d) {
if (tr[p].l == x && tr[p].r == x) {
tr[p].val = d;
tr[p].maxl = tr[p].maxr = tr[p].maxp = tr[p].val;
return ;
}
int mid = (tr[p].l + tr[p].r) >> 1;
if (x <= mid) modify(p << 1 , x , d);
else modify(p << 1 | 1 , x , d);
update(p);
}
int query(int p , int l , int r) {
int ls = p << 1;
int rs = p << 1 | 1;
if (l <= tr[p].l && tr[p].r <= r) return tr[p].maxp;
int mid = (tr[p].l + tr[p].r) >> 1;
if (l > mid) return query(rs , l , r);
if (r <= mid) return query(ls , l , r);
if (l <= mid && r > mid) {
int lans = query(ls , l , r);
int rans = query(rs , l , r);
int mans = getr(ls , l , r) + getl(rs , l , r);
return max2(lans , rans , mans);
}
}
```