题意翻译
nn 个数，qq 次操作
操作0 x y把A_xAx? 修改为yy
操作1 l r询问区间[l, r][l,r] 的最大子段和
感谢 @Edgration 提供的翻译
题目描述
You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
输入输出格式
输入格式：
The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
输出格式：
For each query, print an integer as the problem required.
输入输出样例
输入样例#1： 复制
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3输出样例#1： 复制
6
4
-3分析：
见这篇博客
https://blog.csdn.net/SSL_ZYC/article/details/81951129
数组线段树模板：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
using namespace std;
const double eps = 1e-8;
typedef long long LL;
#define lson i<<1, l, m /// i*2
#define rson i<<1|1, m+1, r /// i*2+1
const int maxn=500000+5;
//线段树需要维护的信息
int sum[maxn*4]; //四倍
int lmaxn[maxn*4],rmaxn[maxn*4],dat[maxn*4];
int a[maxn],ans,pre;
///区间和sumsum，区间最大连续字段和datdat，
///紧靠左端的最大连续字段和lmaxlmax,紧靠右端的最大连续字段和rmaxrmax//i节点收集子节点的统计结果
void PushUp(int i) //求和
{sum[i]=sum[i<<1]+sum[i<<1|1];lmaxn[i]=max(lmaxn[i<<1], sum[i<<1]+lmaxn[i<<1|1]);rmaxn[i]=max(rmaxn[i<<1|1],sum[i<<1|1]+rmaxn[i<<1]);dat[i]=max(max(dat[i<<1], dat[i<<1|1]),lmaxn[i<<1|1]+rmaxn[i<<1]);
}//递归建立线段树
void build(int i,int l,int r)
{if(l==r){sum[i]=a[l];lmaxn[i]=a[l];rmaxn[i]=a[l];dat[i]=a[l];return ;}int m=(l+r)>>1;build(lson);build(rson);PushUp(i);//收集子节点的结果
}//在当前区间[l, r]内查询区间[ql, qr]间的目标值
//且能执行这个函数的前提是：[l,r]与[ql,qr]的交集非空
//其实本函数返回的结果也是 它们交集的目标值
void query(int ql,int qr,int i,int l,int r)
{//目的区间包含当前区间if(ql<=l && r<=qr) {ans=max(ans,dat[i]);//计算ans=max(ans,pre+lmaxn[i]);pre=max(rmaxn[i],pre+sum[i]);//维护prereturn ;}int m=(l+r)>>1;int res=0;if(ql<=m) query(ql,qr,lson);if(m<qr) query(ql,qr,rson);
}
//本题是单点更新，所以是在区间[l,r]内使得第id数的值+val
//如果是区间更新，可以update的参数需要将id变为ql和qr
void update(int id,int val,int i,int l,int r)
{if(l==r){sum[i] = val;lmaxn[i]=val;rmaxn[i]=val;dat[i]=val;return ;}int m=(l+r)>>1;if(id<=m) update(id,val,lson);else update(id,val,rson);PushUp(i);//时刻记住维护i节点统计信息正确性
}
int main()
{int n;//节点总数while(scanf("%d",&n)!=-1){for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);//建立线段树int b,u,v;int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&b,&u,&v);if(b==1) {ans=-1e9;pre=-1e9;if(u>v) swap(u,v);query(u,v,1,1,n);printf("%d\n",ans);}else if(b==0) update(u,v,1,1,n);}}return 0;
}
结构体线段树代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500006, INF = 0x3f3f3f3f;
int n, m, a[N];
struct T {int l, r, sum, lx, rx, ans;
} tree[N*4];
void pushup(int p){tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;tree[p].lx = max(tree[p<<1].lx, tree[p<<1].sum + tree[p<<1|1].lx);tree[p].rx = max(tree[p<<1|1].rx, tree[p<<1].rx + tree[p<<1|1].sum);tree[p].ans = max(max(tree[p<<1].ans, tree[p<<1|1].ans), tree[p<<1].rx + tree[p<<1|1].lx);
}
void build(int p, int l, int r) {tree[p].l = l;tree[p].r = r;if (l == r) {tree[p].sum = tree[p].lx = tree[p].rx = tree[p].ans = a[l];return;}int mid = (l + r) >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);pushup(p);
}void change(int p, int x, int y) {if (tree[p].l == tree[p].r) {tree[p].sum = tree[p].lx = tree[p].rx = tree[p].ans = y;return;}int mid = (tree[p].l + tree[p].r) >> 1;if (x <= mid) change(p << 1, x, y);else change(p << 1 | 1, x, y);pushup(p);
}T ask(int p, int l, int r) {if (l <= tree[p].l && r >= tree[p].r) return tree[p];T a, b, ans;a.sum = a.lx = a.rx = a.ans = b.sum = b.lx = b.rx = b.ans = -INF;ans.sum = 0;int mid = (tree[p].l + tree[p].r) >> 1;if (l <= mid) {a = ask(p << 1, l, r);ans.sum += a.sum;}if (r > mid) {b = ask(p << 1 | 1, l, r);ans.sum += b.sum;}ans.ans = max(max(a.ans, b.ans), a.rx + b.lx);ans.lx = max(a.lx, a.sum + b.lx);ans.rx = max(b.rx, b.sum + a.rx);if (l > mid) ans.lx = max(ans.lx, b.lx);if (r <= mid) ans.rx = max(ans.rx, a.rx);return ans;
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) scanf("%d", &a[i]);build(1, 1, n);while (m--) {int t, x, y;scanf("%d %d %d", &t, &x, &y);if (t == 1) {if (x > y) swap(x, y);cout << ask(1, x, y).ans << endl;}else change(1, x, y);}return 0;
}