動態(tài)區(qū)間最大子序和問題
【問題描述】
給出一個序列A[0..N-1]和M個操作，每個操作都是以下三種之一：
①：查詢區(qū)間最大子序和操作
格式：1 l r
表示：查詢A[l..r]內的最大子序和（就是A[l..r]內的和最大的連續(xù)子序列的和），0<=l<=r<N；
②：修改單個值操作
格式：2 i x
表示：將A[i]的值改為x，0<=i<N；
③：修改整段值操作
格式：3 l r x
表示：將A[l..r]的值全部改為x，0<=l<=r<N。
【具體題目】TYVJ1427（只支持前兩個操作）
【分析】
由于本題是對區(qū)間進行的操作，很自然的想到線段樹，但是線段樹的結點該記錄哪些信息？
首先，區(qū)間內最大子序和的值是一定要維護的，將其記為midmax。然后，由于該區(qū)間的和最大的連續(xù)子序列可能完全位于其左半段中或右半段中，也可能跨越左半段和右半段，并且在跨越的時候，這個最大子序列必然是跨越了左半段的右端和右半段的左端，所以對于結點還需要維護兩個值：區(qū)間左端最大子序和的值（就是從該區(qū)間最左元素開始的連續(xù)子序列的最大和，記為lmax）和區(qū)間右端最大子序和的值（就是在該區(qū)間最右元素終止的連續(xù)子序列的最大和，記為rmax），可以發(fā)現(xiàn)，只記錄這三個值還不能進行維護，還需要記錄一個值sum，表示該區(qū)間內所有元素值的和，這時，可以進行維護了：
p->sum = p->lch->sum + p->rch->sum;
p->lmax = max(p->lch->lmax, p->lch->sum + p->rch->lmax);
p->rmax = max(p->lch->rmax, p->rch->sum + p->lch->rmax);
p->midmax = max(p->lch->midmax, p->rch->midmax, p->lch->rmax + p->rch->lmax);
邊界（對于葉結點）：
p->sum = p->lmax = p->rmax = p->midmax = x;（x是該葉結點的元素值）
然后，考慮各個操作：
①：查詢區(qū)間最大子序和操作
很明顯，要將A[l..r]表示成若干個結點區(qū)間的并。設這些結點從左到右依次為p[1]、p[2]……p[S]。
設F1[i]為p[1..i]中
可繼續(xù)延伸的最大子序和（就是該子序列在p[i]的右端終止），F(xiàn)0[i]為p[1..i]中
不可繼續(xù)延伸的最大子序和（就是該子序列不在p[i]的右端終止），則
F0[i] = max(p[i]->midmax, F1[i - 1] + p[i]->lmax);
F1[i] = max(p[i]->rmax, F1[i - 1] + p[i]->sum);
邊界：F0[0] = F1[0] = 0;
然后，取F0、F1中出現(xiàn)的最大值，就是本次查詢的結果。
具體實現(xiàn)時，不需保存所有F0、F1的值，可用迭代實現(xiàn)（因為F0、F1均只和上一階段的F1值有關）。
②：修改單個值操作
這個很容易實現(xiàn)，只需直接修改即可，注意改完后，該葉結點的所有上層結點的sum、lmax、rmax、midmax值都要重新維護。
③：修改整段值操作
這個比操作②稍難一點，但其實也很容易，只要引入一個標記即可。每當某結點被打上標記x（表示該結點被整體賦值為x）操作之后，將其sum值改為(r-l+1)*x，lmax、rmax和midmax值則需要視x的符號而定：若x>=0，lmax=rmax=midmax=sum；若x<0，lmax=rmax=midmax=x。剩下的就是維護標記了。
總之，這個模型是一個很好的線段樹模型，思考難度適中，但真正實現(xiàn)起來又不是很容易……
代碼（TYVJ1427，時間賊長，用ZKW樹的神犇不要鄙視）：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = 500000, INF = ~0U >> 2;
struct tree {
int l, r, sum, lmax, rmax, midmax;
tree *lch, *rch;
} *t0 = 0;
int n, st[MAXN], a, b, f0, f1, res;
inline int max(int s1, int s2) {return s1 >= s2 ? s1 : s2;}
inline int max(int s1, int s2, int s3) {
int max0 = max(s1, s2);
return max0 >= s3 ? max0 : s3;
}
void mkt(tree *&t1, int l0, int r0)
{
t1 = new tree;
t1->l = l0; t1->r = r0; t1->lch = t1->rch = 0;
if (l0 == r0) t1->sum = t1->lmax = t1->rmax = t1->midmax = st[l0]; else {
int mid = l0 + r0 >> 1;
mkt(t1->lch, l0, mid); mkt(t1->rch, mid + 1, r0);
t1->sum = t1->lch->sum + t1->rch->sum;
t1->lmax = max(t1->lch->lmax, t1->lch->sum + t1->rch->lmax);
t1->rmax = max(t1->rch->rmax, t1->lch->rmax + t1->rch->sum);
t1->midmax = max(t1->lch->midmax, t1->rch->midmax, t1->lch->rmax + t1->rch->lmax);
}
}
void opr1(tree *t1)
{
int l0 = t1->l, r0 = t1->r;
if (l0 > b || r0 < a) return;
if (l0 >= a && r0 <= b) {
f0 = max(t1->midmax, f1 + t1->lmax);
f1 = max(t1->rmax, f1 + t1->sum);
if (f0 > res) res = f0;
if (f1 > res) res = f1;
return;
}
opr1(t1->lch); opr1(t1->rch);
}
void opr2(tree *&t1)
{
int l0 = t1->l, r0 = t1->r;
if (l0 > a || r0 < a) return;
if (l0 == r0) {
t1->sum = t1->lmax = t1->rmax = t1->midmax = b;
return;
}
opr2(t1->lch); opr2(t1->rch);
t1->sum = t1->lch->sum + t1->rch->sum;
t1->lmax = max(t1->lch->lmax, t1->lch->sum + t1->rch->lmax);
t1->rmax = max(t1->rch->rmax, t1->lch->rmax + t1->rch->sum);
t1->midmax = max(t1->lch->midmax, t1->rch->midmax, t1->lch->rmax + t1->rch->lmax);
}
void solve()
{
int m, x;
scanf("%d%d", &n, &m);
re(i, n) scanf("%d", &st[i]);
mkt(t0, 0, n - 1);
re(i, m) {
scanf("%d%d%d", &x, &a, &b); a--;
if (x == 1) {
if (a > --b) {int tmp = a; a = b; b = tmp;}
f0 = f1 = 0; res = -INF;
opr1(t0);
printf("%d\n", res);
} else opr2(t0);
}
}
int main()
{
solve();
return 0;
}
【擴展1】動態(tài)區(qū)間最大空當問題：
一個01序列（就是每個元素都是0或1的序列），一開始為全0，三個操作：
?將一段全0的連續(xù)子序列改為全1；
‚將一段全1的連續(xù)子序列改為全0；
ƒ求整個序列的最大空當（就是長度最大的全0連續(xù)子序列的長度）
（其實第
ƒ個操作是可以加強的：求一段給定區(qū)間內的最大空當，這時就需要按照上面的動態(tài)區(qū)間最大子序和問題一樣，分別處理了）
【具體題目】
PKU1823有了上一個模型，這個模型直接秒掉（類似地搞即可）
代碼：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
struct tree {
int l, r, len, lfe, rte, mide, mk;
tree *lch, *rch;
} *t0 = 0;
int n, a, b, res = 0;
bool mk0;
inline int max(int s1, int s2, int s3) {
int s0 = s1 >= s2 ? s1 : s2;
return s0 >= s3 ? s0 : s3;
}
void mkt(tree *&t1, int l0, int r0)
{
t1 = new tree;
t1->l = l0; t1->r = r0; t1->lfe = t1->rte = t1->mide = t1->len = r0 - l0 + 1; t1->mk = -1; t1->lch = t1->rch = 0;
if (l0 < r0) {int mid = l0 + r0 >> 1; mkt(t1->lch, l0, mid); mkt(t1->rch, mid + 1, r0);}
}
void solve(tree *&t1)
{
int l0 = t1->l, r0 = t1->r;
if (l0 > b || r0 < a) return;
if (l0 >= a && r0 <= b) {
t1->mk = mk0;
if (mk0) t1->lfe = t1->rte = t1->mide = 0; else t1->lfe = t1->rte = t1->mide = t1->len;
return;
}
if (!t1->mk) {
t1->mk = -1;
t1->lch->mk = 0; t1->lch->lfe = t1->lch->rte = t1->lch->mide = t1->lch->len;
t1->rch->mk = 0; t1->rch->lfe = t1->rch->rte = t1->rch->mide = t1->rch->len;
}
if (t1->mk == 1) {
t1->mk = -1;
t1->lch->mk = 1; t1->lch->lfe = t1->lch->rte = t1->lch->mide = 0;
t1->rch->mk = 1; t1->rch->lfe = t1->rch->rte = t1->rch->mide = 0;
}
solve(t1->lch); solve(t1->rch);
if (t1->lch->lfe == t1->lch->len) t1->lfe = t1->lch->len + t1->rch->lfe; else t1->lfe = t1->lch->lfe;
if (t1->rch->rte == t1->rch->len) t1->rte = t1->lch->rte + t1->rch->len; else t1->rte = t1->rch->rte;
t1->mide = max(t1->lch->mide, t1->rch->mide, t1->lch->rte + t1->rch->lfe);
}
int main()
{
int m, x;
scanf("%d%d", &n, &m);
mkt(t0, 0, n - 1);
re(i, m) {
scanf("%d", &x);
if (x == 1) {
mk0 = 1;
scanf("%d%d", &a, &b); b += --a; b--;
solve(t0);
}
if (x == 2) {
mk0 = 0;
scanf("%d%d", &a, &b); b += --a; b--;
solve(t0);
}
if (x == 3) printf("%d\n", t0->mide);
}
return 0;
}