传送门

首先考虑暴力做法，可以先求一遍前缀和 sum，然后ans = max(ans, sum[i] sum[k]) (i q <= k <= i p)

但这个肯定会超时。

仔细看这个公式，sum[i] 不变，只用求最小 sum[k] 就行，所以可以用单调队列维护这个区间的最小 sum[k]。

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define LL long long 4 5 using namespace std; 6 7 const int MAXN = 100010; 8 int n, p, q, h = 1, t; 9 LL a[MAXN], que[MAXN], ans = 0x7fffffff; 10 11 int main() 12 20 for(i = p; i <= n; i++) 21 27 printf("%lld", ans); 28 return 0; 29 }
View Code