動態(tài)區(qū)間最大子序和問題
【問題描述】
給出一個序列A[0..N-1]和M個操作，每個操作都是以下三種之一：
①：查詢區(qū)間最大子序和操作
格式：1 l r
表示：查詢A[l..r]內(nèi)的最大子序和（就是A[l..r]內(nèi)的和最大的連續(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ū)間進行的操作，很自然的想到線段樹，但是線段樹的結(jié)點該記錄哪些信息？
首先，區(qū)間內(nèi)最大子序和的值是一定要維護的，將其記為midmax。然后，由于該區(qū)間的和最大的連續(xù)子序列可能完全位于其左半段中或右半段中，也可能跨越左半段和右半段，并且在跨越的時候，這個最大子序列必然是跨越了左半段的右端和右半段的左端，所以對于結(jié)點還需要維護兩個值：區(qū)間左端最大子序和的值（就是從該區(qū)間最左元素開始的連續(xù)子序列的最大和，記為lmax）和區(qū)間右端最大子序和的值（就是在該區(qū)間最右元素終止的連續(xù)子序列的最大和，記為rmax），可以發(fā)現(xiàn)，只記錄這三個值還不能進行維護，還需要記錄一個值sum，表示該區(qū)間內(nèi)所有元素值的和，這時，可以進行維護了：
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);
邊界（對于葉結(jié)點）：
p->sum = p->lmax = p->rmax = p->midmax = x;（x是該葉結(jié)點的元素值）

然后，考慮各個操作：
①：查詢區(qū)間最大子序和操作
很明顯，要將A[l..r]表示成若干個結(jié)點區(qū)間的并。設這些結(jié)點從左到右依次為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)的最大值，就是本次查詢的結(jié)果。
具體實現(xiàn)時，不需保存所有F0、F1的值，可用迭代實現(xiàn)（因為F0、F1均只和上一階段的F1值有關(guān)）。
②：修改單個值操作
這個很容易實現(xiàn)，只需直接修改即可，注意改完后，該葉結(jié)點的所有上層結(jié)點的sum、lmax、rmax、midmax值都要重新維護。
③：修改整段值操作
這個比操作②稍難一點，但其實也很容易，只要引入一個標記即可。每當某結(jié)點被打上標記x（表示該結(jié)點被整體賦值為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樹的神犇不要鄙視）：

【擴展1】動態(tài)區(qū)間最大空當問題：
一個01序列（就是每個元素都是0或1的序列），一開始為全0，三個操作：
?將一段全0的連續(xù)子序列改為全1；
‚將一段全1的連續(xù)子序列改為全0；
ƒ求整個序列的最大空當（就是長度最大的全0連續(xù)子序列的長度）
（其實第ƒ個操作是可以加強的：求一段給定區(qū)間內(nèi)的最大空當，這時就需要按照上面的動態(tài)區(qū)間最大子序和問題一樣，分別處理了）
【具體題目】PKU1823
有了上一個模型，這個模型直接秒掉（類似地搞即可）
代碼：