[洛谷P4513]小白逛公园
题目大意：有一段数列，有两个操作
- $1,a,b：$求出$[a,b]$内最大子段和
- $2,p,s：$把第$p$个数改为$s$
题解：线段树，记录区间最大前缀，最大后缀，区间和以及区间的答案
卡点：1.题目说可能$ageqslant b$
C++ Code：
#include <cstdio>
#define maxn 500010
using namespace std;
int n, m;
inline int max(int a, int b) {return a > b ? a : b;}
struct node {
int l, r, sum, mx;
inline node operator + (const node &rhs) {
node res;
res.l = max(l, sum + rhs.l);
res.r = max(r + rhs.sum, rhs.r);
res.sum = sum + rhs.sum;
res.mx = max(max(mx, rhs.mx), r + rhs.l);
return res;
}
} s[maxn << 2];
void add(int rt, int l, int r, int p, int num) {
if (l == r) {
s[rt].l = s[rt].r = s[rt].sum = s[rt].mx = num;
return ;
}
int mid = l + r >> 1;
if (p <= mid) add(rt << 1, l, mid, p, num);
else add(rt << 1 | 1, mid + 1, r, p, num);
s[rt] = s[rt << 1] + s[rt << 1 | 1];
}
node ask(int rt, int l, int r, int L, int R) {
if (L == l && R == r) return s[rt];
int mid = l + r >> 1;
if (R <= mid) return ask(rt << 1, l, mid, L, R);
if (L > mid) return ask(rt << 1 | 1, mid + 1, r, L, R);
return ask(rt << 1, l, mid, L, mid) + ask(rt << 1 | 1, mid + 1, r, mid + 1, R);
}
inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
add(1, 1, n, i, a);
}
while (m --> 0) {
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if (k == 1) {
if (x > y) swap(x, y);
printf("%d
", ask(1, 1, n, x, y).mx);
} else add(1, 1, n, x, y);
}
return 0;
}