题意:给定一个长度为n的序列,m个询问[a,b],求[a,b]间最大子段和的开头和结尾。

思路:用线段树解答,每个节点保存对应段的最大前缀的结尾位置,最大后缀的开头位置,最大子段的开头结尾位置。询问时将[a,b]间的线段数中的区间从左到右依次取出,保存为约log2(b-a)个子段,求这log2(b-a)个区间所构成的最大子段和。

由于最大子段在这些区间中只有如下三种可能性:

其中红色部分为最大子段。

显然最大子段只可能包括1.某个区间A的最大后缀、某个区间B的最大前缀、和这两个区间中的所有区间(可以没有)。或者 2.某个区间的最大子段。所以可以枚举情况2(即图中情况2),并用O(N)(即原题的O(log2n))求出情况1(即图中情况1、3)最大子段。取两者最大值。

然而,不知为何,这个程序评测总是WA,对拍10000组随机、极限、手写数据都没问题。发现错误请赶快来裱我。