Can you answer these queries III

题意

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

操作$0xy$把$A_x$修改为$y$

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

输入输出样例

输入

4 1 2 3 4 4 1 1 3 0 3 -3 1 2 4 1 3 3

输出

6 4 -3 /*** Amber ***/ //#pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <cstring> #include <set> #include <map> #include <cmath> #include <queue> #include <algorithm> #include <vector> using namespace std; #define ls (rt<<1) #define rs (rt<<1|1) const double Pi=acos(-1); const double eps=1e-6; const int mod = 1e9+7; const int inf = 0x3f3f3f3f; const int maxn = 5e4+10; int n; struct node{ int sum,lsum,rsum,ans; }t[maxn << 2]; int a[maxn]; void pushup(int rt) { t[rt].sum = t[ls].sum + t[rs].sum; t[rt].lsum = max(t[ls].sum + t[rs].lsum, t[ls].lsum); t[rt].rsum = max(t[rs].sum + t[ls].rsum, t[rs].rsum); t[rt].ans = max(t[ls].ans, max(t[rs].ans, t[ls].rsum + t[rs].lsum)); } void build(int rt,int l,int r) { if (l == r) { t[rt].ans = t[rt].lsum = t[rt].rsum = t[rt].sum = a[l]; return; } int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); pushup(rt); } void change(int rt,int l,int r,int x,int k) { if (l == r) { t[rt].ans = t[rt].lsum = t[rt].rsum = t[rt].sum = k; return; } int mid = l + r >> 1; if (x <= mid) change(ls, l, mid, x, k); else change(rs, mid + 1, r, x, k); pushup(rt); } node query(int rt,int l,int r,int ql,int qr) { if (ql <= l && r <= qr) { return t[rt]; } int mid = l + r >> 1; if (qr <= mid) return query(ls, l, mid, ql, qr); if (ql > mid) return query(rs, mid + 1, r, ql, qr); node L = query(ls, l, mid, ql, qr), R = query(rs, mid + 1, r, ql, qr); node res; res.sum = L.sum + R.sum; res.ans = max(L.ans,max(R.ans,R.lsum+L.rsum)); res.lsum = max(L.lsum, L.sum + R.lsum); res.rsum = max(R.rsum, R.sum + L.rsum); return res; } inline void work() { scanf("%d",&n); for (int i = 1; i <= n; i++) { scanf("%d",&a[i]); } build(1, 1, n); int q; scanf("%d",&q); while (q--) { int op, x, y; scanf("%d%d%d",&op,&x,&y); if (op == 0) { change(1, 1, n, x, y); } else { printf("%d\n", query(1, 1, n, x, y).ans); } } } int main() { work(); return 0; }