给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤ymaxx≤l≤r≤y{∑ri=lA[i]∑i=lrA[i]}。
2、“2 x y”，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。
输出格式
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
数据范围
N≤500000,M≤100000N≤500000,M≤100000
输入样例：
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
输出样例：
2
-1
算法：线段树最大子段和
代码：
#include <iostream> #include <cstdio> using namespace std; #define INF 0x3f3f3f3f const int maxn = 5e5+7; struct node { int ms; //存储当前区间最大子段和 int lmax; //左边得前缀和 int rmax //右边得前缀和 int sum; //这个区间的总和 }tree[maxn << 2]; int arr[maxn]; int n, m; void pushup(int root) { //参数的解释： tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum; //左子数的总和 + 右子树的总和 tree[root].lmax = max(tree[root << 1].lmax, tree[root << 1].sum + tree[root << 1 | 1].lmax); //左子数左边得前缀和，左子数得总和 + 右子树左边的前缀和 tree[root].rmax = max(tree[root << 1 | 1].rmax, tree[root << 1 | 1].sum + tree[root << 1].rmax); //右子树右边的前缀和，右子树的总和 + 左子数右边的前缀和 tree[root].ms = max(max(tree[root << 1].ms, tree[root << 1 | 1].ms), tree[root << 1].rmax + tree[root << 1 | 1].lmax); //左子树的区间最大子段和，右子树的区间最大子段和，左子数右边的前缀和 + 右子树左边的前缀和 } void build(int root, int l ,int r) { if(l == r) { tree[root].sum = arr[l]; tree[root].ms = arr[l]; tree[root].lmax = arr[l]; tree[root].rmax = arr[l]; return; } int mid = (l + r) >> 1; build(root << 1, l ,mid); build(root << 1 | 1, mid + 1, r); pushup(root); } void update(int root, int l, int r, int x, int y) { if(l == r) { tree[root].sum = y; tree[root].ms = y; tree[root].lmax = y; tree[root].rmax = y; return; } int mid = (l + r) >> 1; if(x <= mid) { update(root << 1, l, mid, x, y); } else { update(root << 1 | 1, mid + 1, r, x, y); } pushup(root); } struct node query(int root, int l, int r, int x, int y) { if(x <= l && r <= y) { return tree[root]; } int mid = (l + r) >> 1; struct node a, b, c; //首先初始化，因为有可能进入第一种或者是第二种情况，那么其中有一个变量就用不到 a.ms = a.lmax = a.rmax = a.sum = -INF; b.ms = b.lmax = b.rmax = b.sum = -INF; c.ms = c.lmax = c.rmax = -INF; c.sum = 0; //分三种情况： if(x <= mid && y <= mid) { a = query(root << 1, l, mid, x, y); c.sum += a.sum; } else if(x > mid && y > mid) { b = query(root << 1 | 1, mid + 1, r, x, y); c.sum += b.sum; } else { a = query(root << 1, l, mid, x, y); b = query(root << 1 | 1, mid + 1, r, x, y); c.sum += a.sum + b.sum; } //解释同上... c.ms = max(c.ms, max(a.rmax + b.lmax, max(a.ms, b.ms))); c.lmax = max(c.lmax, max(a.lmax, a.sum + b.lmax)); c.rmax = max(c.rmax, max(b.rmax, b.sum + a.rmax)); return c; } int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &arr[i]); } build(1, 1, n); while(m--) { int q, x, y; scanf("%d %d %d", &q, &x, &y); if(q == 1) { if(x > y) { //题目中有解释... swap(x, y); } printf("%d\n", query(1, 1, n, x, y).ms); } else { update(1, 1 ,n, x, y); } } return 0; }