原题地址：http://acm.uestc.edu.cn/#/problem/show/844
“你动规无力，图论不稳，数据结构松散，贪心迟钝，没一样像样的，就你还想和我同台竞技，做你的美梦！今天这场比赛，就是要让你知道你是多么
的无能！！”
不训练，无以为战。有n项能力是ACM竞赛要求的，训练则能提升，忽略则会荒废。
这m天，你能做到如何。
Input
第一行两个整数n，m,分别表示有n项能力要求，共有m天。
第二行n个整数，第i个整数ai表示第i项能力的数值。
接下来m行，每行开始先读入一个整数si，表明这是一次询问还是一次能力变化。
si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问在[li，ri]区间中任选一段连续序列，这段序列中所有能力值之和最大能是多少。
si=1，表明这是一次能力变化，然后读入两个整数xi,wi，表示第xi项能力变为了wi。
1≤n,m≤100000,−10000≤ai≤10000,1≤li≤ri≤n,1≤xi≤n,−10000≤wi≤10000
Output
有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。
Sample input and output
| Sample Input | Sample Output |
|---|---|
4 41 2 3 40 1 31 3 -30 2 40 3 3 | 64-3 |
此题使用线段树解决。不过与一般的线段树不同，这道题需要用到4个sum变量。考虑每一个节点sequ[now]，令其和为sum，连接到其最左边的值的
子串的最大和为sum1，连接到其最右边的值的字串的最大和为sum2，另其连续字串的最大和为sum0。则有以下四个等式：
sequ[now].sum = sequ[2 * now].sum + sequ[2 * now + 1].sum;
sequ[now].sum0 = max(sequ[2 * now].sum2, max(sequ[2 * now].sum2 + sequ[2 *now + 1].sum1, max(sequ[2 *now + 1].sum1,max(sequ[2*now].su
m0,sequ[2*now+1].sum0))));
sequ[now].sum1 = max(sequ[2 * now].sum1, sequ[2 * now].sum + sequ[2 * now + 1].sum1);
sequ[now].sum2 = max(sequ[2 * now + 1].sum2, sequ[2 * now + 1].sum + sequ[2 *now].sum2);
这样维护的线段树，就能得到每一个节点的各个最值。然后在询问时使用深搜，从下往上，用和更新时同样的思想，维护不断连接的区间的各个最值，
最后输出sum0，便是得到的最值。详见代码。
#include#include #include #include #define MAX_N 100005#define MAX_M 100005using namespace std;struct node{ int left, right, sum0, sum1, sum2, sum; node() { sum0 = sum1 = sum2 = sum = 0; }};node sequ[4 * MAX_N + 1000];stack st;void build(int x, int l, int r){ sequ[x].left = l; sequ[x].right = r; if (l != r) { int k = (l + r) / 2; build(2 * x, l, k); build(2 * x + 1, k + 1, r); }}void update(int now, int n, int a){ if (sequ[now].left == n&&sequ[now].right == n) sequ[now].sum = sequ[now].sum0 = sequ[now].sum1 = sequ[now].sum2 = a; else { int k = (sequ[now].left + sequ[now].right) / 2; if (k >= n) update(2 * now, n, a); else update(2 * now + 1, n, a); sequ[now].sum = sequ[2 * now].sum + sequ[2 * now + 1].sum; sequ[now].sum0 = max(sequ[2 * now].sum2, max(sequ[2 * now].sum2 + sequ[2 * now + 1].sum1, max(sequ[2 * now + 1].sum1 ,max(sequ[2*now].sum0,sequ[2*now+1].sum0)))); sequ[now].sum1 = max(sequ[2 * now].sum1, sequ[2 * now].sum + sequ[2 * now + 1].sum1); sequ[now].sum2 = max(sequ[2 * now + 1].sum2, sequ[2 * now + 1].sum + sequ[2 * now].sum2); }}void ask(int l, int r, int now){ if (sequ[now].left == l&&sequ[now].right == r) st.push(now); else { int k = (sequ[now].right + sequ[now].left) / 2; if (k < l) ask(l, r, now * 2 + 1); else if (k >= r) ask(l, r, now * 2); else { ask(l, k, now * 2); ask(k + 1, r, now * 2 + 1); } }}int answer(){ int sumT0 = 0, sumT1 = 0, sumT2 = 0, sumT = 0; int nr, nl; sumT0 = sequ[st.top()].sum0; sumT1 = sequ[st.top()].sum1; sumT2 = sequ[st.top()].sum2; sumT = sequ[st.top()].sum; nr = sequ[st.top()].right; nl = sequ[st.top()].left; st.pop(); while (!st.empty()) { int now = st.top(); st.pop(); if (sequ[now].left == nr) { sumT0 = max(sumT0, max(sequ[now].sum0, max(sequ[now].sum1, max(sumT2, sumT2 + sequ[now].sum1)))); sumT1 = max(sumT1, sumT + sequ[now].sum1); sumT2 = max(sequ[now].sum2, sequ[now].sum + sumT2); sumT = sumT + sequ[now].sum; nr = sequ[now].right; } else { sumT0 = max(sumT0, max(sequ[now].sum0, max(sequ[now].sum2, max(sumT1, sumT1 + sequ[now].sum2)))); sumT1 = max(sequ[now].sum1, sequ[now].sum + sumT1); sumT2 = max(sumT2, sumT + sequ[now].sum2); sumT = sumT + sequ[now].sum; nl = sequ[now].left; } } return sumT0;}int main(){ int n, m; scanf("%d%d", &n, &m); build(1, 1, n); for (int i = 0; i < n; i++) { int a; scanf("%d", &a); update(1, i + 1, a); } for (int i = 0; i < m; i++) { while (!st.empty()) st.pop(); bool p; scanf("%d", &p); if (p) { int x, w; scanf("%d%d", &x, &w); update(1, x, w); } else { int l, r; scanf("%d%d", &l, &r); ask(l, r, 1); printf("%d\n", answer()); } } return 0;}