【題意】：給出一個長度為n的環(huán)狀序列，求一個長度不超過k的和最大的連續(xù)子序列。

【題解】：很容易想到O(n*k)的做法，但是赤裸裸的TLE。
               先求出所有前n項和。
               枚舉每一個位置 i 作為結(jié)束點，現(xiàn)在我們要找到最小的sum[j], i - k <= j < i .
               樸素做法是直接枚舉O(k)，改進一點的做法是用線段樹查詢區(qū)間最大值O(logk).
               但是可以證明有單調(diào)性，故可以用單調(diào)隊列優(yōu)化，查詢直接優(yōu)化到O(1)。
               所以最終復(fù)雜度是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