牛客周赛51 F（静态区间最大连续子段和）

题面

题目地址

原题是SPOJ 1043。本文中我介绍的是维护前缀和的写法，如果你想要了解其他写法，可以搜索原题题解。

题目大意：

给定长度为n的数组a，q次查询，每次询问[l,r]中连续子段和的绝对值最大是多少

1 <= n, q<= 5 x 105

-109 <= a <= 109

1 <= l <= r <= n

思路

数据范围5e5，算法复杂度需要在nlogn左右。

问题在于如何快速的查询[l,r]中连续子段和的最大绝对值。

先想暴力的写法，枚举所有长度的子段和可能性，单次查询复杂度n3

for(int len = 1; len <= n; i++){ //枚举长度 for(int i = 1; i <= n - len + 1; i++){ //枚举起点 int sum = abs(accumulate(v.begin() + i, v.begin() + i + len)); //记录最大值，省略 } } 123456

很显然有一个简单的优化方法，前缀和（不懂自查），单次查询复杂度到了n2

for(int i = L; i <= R; i++){ for(int j = i + 1; j <= R; j++){ int sum = abs(s[j] - s[i-1]); //记录最大值，省略 } } 123456

仔细考虑一下，上文的前缀和在做什么事？枚举所有的s[i]可能性，然后找到最大值。这里的最大值是如何得来的？最大的s[i] - 最小的s[i]。

所以，还可以进一步优化。单词查询时间复杂度到了n。

for(int i = L - 1; i <= R; i++){ minm = min(minm, s[i]); maxm = max(maxm, s[i]); } 1234

虽然我们已经进行了不少优化，但是总体复杂度n2对我们来说还是太高了。现在问题关键在于，如何用logn的复杂度，查询区间最大值、最小值。

这样就很简单了，可以用st表、线段树等维护前缀和来实现。很简单就不赘述了。