单调递减队列是这么一个队列，它的头元素一直是队列当中的最大值，而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素，可以从队列的两端删除元素。
1.首先看插入元素：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v,这个时候我们才将v插入到队尾。
2.队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时，将队首元素删除。
于是这题可以用两个单调队列来做，一个维护最大值，一个维护最小值，当不满足条件时，更改在序列前面的那个
最值。
代码(单调队列)
#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;const int inf=0x7fffffff;const int maxn=100000+100;int l[maxn];int r[maxn];struct node{int x;int cur;}a[maxn],b[maxn],p;int main(){int t;scanf("%d",&t);while(t–){int n,k;scanf("%d%d",&n,&k);int cur=1;scanf("%d",&a[1].x);a[1].cur=b[1].cur=1;b[1].x=a[1].x;int front1=1,front2=1;int cur1=1,cur2=1;long long ans=1;for(int i=2;i<=n;i++){scanf("%d",&p.x);p.cur=i;for(int j=cur1;j>=front1;j–)//维护最大值{if(p.x<=a[j].x){a[j+1].x=p.x;a[j+1].cur=p.cur;cur1=j+1;break;}if(j==front1){a[front1].x=p.x;a[front1].cur=p.cur;cur1=front1;break;}}for(int j=cur2;j>=front2;j–)//维护最小值{if(p.x>=b[j].x){b[j+1].x=p.x;b[j+1].cur=p.cur;cur2=j+1;break;}if(j==front2){b[front2].x=p.x;b[front2].cur=p.cur;cur2=front2;break;}}while(a[front1].x-b[front2].x>=k)//不满足条件{if(a[front1].cur<b[front2].cur)//删除最大值{cur=a[front1].cur+1;//区间长度在删除前向后移1位front1++;}else{cur=b[front2].cur+1;front2++;}}ans=ans+(i-cur+1);}printf("%I64d\n",ans);}return 0;}
代码(multiset)
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<set>using namespace std;int n,k,num[100010];int main(){// freopen("D:\\in.txt","r",stdin);int T,i,j;cin>>T;while(T–){cin>>n>>k;multiset<int> ss;multiset<int>::iterator it;multiset<int>::reverse_iterator itt;for(i=0;i<n;i++)scanf("%d",&num[i]);int st=0,ed=0;int mi=num[0],ma=num[0];long long ans=0;while(st<n){while(ed<n){if(num[ed]<=ma&&num[ed]>=mi){ss.insert(num[ed++]);continue;}if(num[ed]<mi){if(ma-num[ed]<k){mi=num[ed];ss.insert(num[ed++]);continue;}else{ed–;break;}}if(num[ed]>ma){if(num[ed]-mi<k){ma=num[ed];ss.insert(num[ed++]);continue;}else{ed–;break;}}}if(ed==n) ed–;ans+=ed-st+1;it=ss.find(num[st]);ss.erase(it);if(!ss.empty()){it=ss.begin();mi=*it;itt=ss.rbegin();ma=*itt;}else{mi=ma=num[st+1];}st++;if(st>ed)ed=st;elseed++;}cout<<ans<<endl;}}
，问候不一定要慎重其事，但一定要真诚感人
