題目大意：給出一個有N個數(shù)字（-1000..1000，N<=10^5）的環(huán)狀序列，讓你求一個和最大的連續(xù)子序列。這個連續(xù)子序列的長度小于等于K。
分析：因?yàn)樾蛄惺黔h(huán)狀的，所以可以在序列后面復(fù)制一段（或者復(fù)制前k個數(shù)字）。如果用s[i]來表示復(fù)制過后的序列的前i個數(shù)的和，那么任意一個子序列[i..j]的和就等于s[j]-s[i-1]。對于每一個j，用s[j]減去最小的一個s[i](i>=j-k+1)就可以得到以j為終點(diǎn)長度不大于k的和最大的序列了。將原問題轉(zhuǎn)化為這樣一個問題后，就可以用單調(diào)隊(duì)列解決了。
單調(diào)隊(duì)列即保持隊(duì)列中的元素單調(diào)遞增（或遞減）的這樣一個隊(duì)列，可以從兩頭刪除，只能從隊(duì)尾插入。單調(diào)隊(duì)列的具體作用在于，由于保持隊(duì)列中的元素滿足單調(diào)性，對于上述問題中的每個j，可以用O(1)的時間找到對應(yīng)的s[i]。（保持隊(duì)列中的元素單調(diào)增的話，隊(duì)首元素便是所要的元素了）。
維護(hù)方法：對于每個j，我們插入s[j-1]（為什么不是s[j]? 隊(duì)列里面維護(hù)的是區(qū)間開始的下標(biāo)，j是區(qū)間結(jié)束的下標(biāo)），插入時從隊(duì)尾插入。為了保證隊(duì)列的單調(diào)性，我們從隊(duì)尾開始刪除元素，直到隊(duì)尾元素比當(dāng)前需要插入的元素優(yōu)（本題中是值比待插入元素小，位置比待插入元素靠前，不過后面這一個條件可以不考慮），就將當(dāng)前元素插入到隊(duì)尾。之所以可以將之前的隊(duì)列尾部元素全部刪除，是因?yàn)樗鼈円呀?jīng)不可能成為最優(yōu)的元素了，因?yàn)楫?dāng)前要插入的元素位置比它們靠前，值比它們小。我們要找的，是滿足(i>=j-k+1)的i中最小的s[i]，位置越大越可能成為后面的j的最優(yōu)s[i]。
在插入元素后，從隊(duì)首開始，將不符合限制條件(i>=j-k+1)的元素全部刪除，此時隊(duì)列一定不為空。（因?yàn)閯倓偛迦肓艘粋€一定符合條件的元素）
#include<iostream>
#include<queue>
using?namespace?std;
#define?INF?0x3fffffff
#define?maxn?100010
int?num[maxn],sum[maxn];
int?main()
{
????int?T;
????int?N,K,n;
????cin>>T;
????while(T--)
????{
????????cin>>N>>K;
????????sum[0]=0;
????????for(int?i=1;i<=N;i++)
????????{
????????????cin>>num[i];
????????????sum[i]=sum[i-1]+num[i];
????????}
????????for(int?i=N+1;i<N+K;i++)
????????{
????????????sum[i]=sum[i-1]+num[i-N];
????????}
????????n=N+K-1;
????????
????????deque<int>?q;
????????q.clear();
????????
????????int?ans=-INF;
????????int?start,end;
????????//[j-k
j]?枚舉以j結(jié)尾的區(qū)間,找[j-k,j]中sum最小的i
????????for(int?j=1;j<=n;j++)
????????{
????????????while(!q.empty()?&&?sum[j-1]<sum[q.back()])
????????????????q.pop_back();
????????????while(!q.empty()?&&?q.front()<(j-K))
????????????????q.pop_front();
????????????q.push_back(j-1);
????????????if(sum[j]-sum[q.front()]>ans)
????????????{
????????????????ans=sum[j]-sum[q.front()];
????????????????start=q.front()+1;
????????????????end=j;
????????????}
????????}
????????cout<<ans<<"?"<<start<<"?"<<(end>N?end%N:end)<<endl;
????}
}