传送门
首先考虑暴力做法，可以先求一遍前缀和 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
上一篇：[luoguP2444] [POI2000]病毒（AC自动机 + dfs）
下一篇：基本数论算法
单调队列
