【题意】：给出一个长度为n的环状序列，求一个长度不超过k的和最大的连续子序列。
【题解】：很容易想到O(n*k)的做法，但是赤裸裸的TLE。
先求出所有前n项和。
枚举每一个位置 i 作为结束点，现在我们要找到最小的sum[j], i - k <= j < i .
朴素做法是直接枚举O(k)，改进一点的做法是用线段树查询区间最大值O(logk).
但是可以证明有单调性，故可以用单调队列优化，查询直接优化到O(1)。
所以最终复杂度是O(n)。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 100050
22 const int inf = 1 << 30;
23 int que[maxn<<1], head, tail;
24 int sum[maxn<<1];
25 int val[maxn];
26 int n, k;
27 int ans, s, t;
28 int main() {
29 int T;
30 scanf("%d", &T);
31 while(T--) {
32 scanf("%d%d", &n, &k);
33 sum[0] = 0;
34 for(int i = 1; i <= n; i++) {
35 scanf("%d", &val[i]);
36 sum[i] = val[i] + sum[i-1];
37 }
38 for(int i = n + 1; i <= 2 * n; i++) {
39 sum[i] = sum[i-1] + val[i-n];
40 }
41 ans = -inf;
42 head = tail = 0;
43 que[tail++] = 0;
44 for(int i = 1; i <= 2 * n; i++) {
45 while(head < tail && que[head] < i - k) head++;
46 if(ans < sum[i] - sum[que[head]]) {
47 ans = sum[i] - sum[que[head]];
48 s = que[head] + 1, t = i;
49 }
50 while(head < tail && sum[que[tail-1]] > sum[i]) tail--;
51 que[tail++] = i;
52 }
53 if(s > n) s -= n;
54 if(t > n) t -= n;
55 cout << ans << " " << s << " " << t << endl;
56 }
57 return 0;
58 }
59