SPOJ GSS系列
这个系列题目内容以维护区间最大子段和为主线。维护这个一般需要维护区间和，区间最大前缀，区间最大后缀，区间最大子段和四个信息。使用结构体封装和重载运算符可以使代码非常好看。
struct node
{
int sum,mix,pre,suf;
node(int Sum=0,int Mix=0,int Pre=0,int Suf=0) {sum=Sum,mix=Mix,pre=Pre,suf=Suf;}
friend node operator + (node a,node b)
{
node res;
res.sum=a.sum+b.sum;
res.pre=max(a.pre,a.sum+b.pre);
res.suf=max(b.suf,b.sum+a.suf);
res.mix=max(max(a.mix,b.mix),a.suf+b.pre);
return res;
}
};
GSS1
板子，把树建出来直接查询即可。查询写的可能和正常的查询不大一样，分成完全在左区间，完全在右区间，跨区间三种情况查询——因为重载了运算符要注意运算顺序。代码
GSS3
板子，加上了单点修改，普通线段树怎么写这个也怎么写。代码
GSS4
这个题真是做烂了啊/tuu。注意到开方操作次数不会太多，维护区间最大值，超过 \(1\) 直接暴力修改区间。代码
GSS5
分类讨论。当 \(r_1 < l_2\) 的时候，\([r_1,l_2]\) 是一定要被选的，求 \([l1,r1)\) 的最大后缀和 \((l2,r2]\) 的最大前缀；若 \(r_1 \geq l_2\)，则答案有三种情况，分别是 \([l_2,r_1]\) 的最大子段和，\([l_1,l_2)\) 的最大后缀加 \([l_2,r_2]\) 的最大前缀，\([l_1,r_1]\) 的最大后缀加 \((r_1,r_2]\) 的最大前缀。为了下面的操作写的好看一点，查询函数里面加个判断 if(l>r)。注意区间开闭防止算重。代码
GSS6
插入删除操作考虑平衡树，在平衡树上每个节点再额外维护一个最大子段和信息就好了，其他的和普通序列操作一样。代码