log数据结构乱做

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\) 直接暴力修改区间。代码

GSS6

插入删除操作考虑平衡树，在平衡树上每个节点再额外维护一个最大子段和信息就好了，其他的和普通序列操作一样。代码