题意：给T足数据，然后每组一个n和k，表示n个数，k表示最大同意的能力差，接下来n个数表示n个人的能力，求能力差在k之内的区间有几个

分析：维护一个区间的最大值和最小值，使得他们的差小于k，于是採用单调队列

普通单调队列做法：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn = 1e6+5;

int a[maxn];

struct node{

    int index;

    int v;

}qd[maxn];

node qx[maxn];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,k;

        scanf("%d%d",&n,&k);

        for(int i=1;i<=n;i++){

            scanf("%d",&a[i]);

        }

        int st1,st2,ed1,ed2;

        st1=st2=ed1=ed2=1;

        long long sum=0;

        int j=1;

        for(int i=1;i<=n&&j<=n;i++){

            if(i==1){

                qd[1].index=qx[1].index=1;

                qd[1].v=qx[1].v=a[1];

            }

            else{

                while(st1<=ed1){                //单调队列维护最大值

                    if(qd[ed1].v<=a[i]) ed1--;  //比a[i]小的并且下标比i小的出队列

                    else break;

                }

                qd[++ed1].v=a[i];               //a[i]入队列

                qd[ed1].index=i;

                while(st2<=ed2){                //单调队列维护最小值

                    if(qx[ed2].v>=a[i]) ed2--;  //比a[i]大并且下标比i小的出队列

                    else break;

                }

                qx[++ed2].v=a[i];               //a[i]入队列

                qx[ed2].index=i;

                while(qd[st1].v-qx[st2].v>=k&&st1<=ed1&&st2<=ed2)   //计数

                {

                    if(qd[st1].index==j) st1++;

                    if(qx[st2].index==j) st2++;

                    sum+=(i-j);

                    j++;

                }

            }

        }

        while(j<=n) {

            sum+=(n-j+1);

            j++;

        }

        printf("%I64d\n",sum);

    }

}

二分单调队列做法：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn = 1e6+5;

int a[maxn];

struct node{

    int index;

    int v;

}qd[maxn];

node qx[maxn];

int maxc(int l,int r,int d){        //二分找出d入队列的为止

    while(l<=r){

        int mid=(l+r)/2;

        if(qd[mid].v==d) return mid;

        else if(qd[mid].v>d) l=mid+1;

        else r=mid-1;

    }

    return l;

}

int minc(int l,int r,int d){        //二分找出d入队列的为止

    while(l<=r){

        int mid=(l+r)/2;

        if(qx[mid].v==d) return mid;

        else if(qx[mid].v<d) l=mid+1;

        else r=mid-1;

    }

    return l;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,k;

        scanf("%d%d",&n,&k);

        for(int i=1;i<=n;i++){

            scanf("%d",&a[i]);

        }

        int st1,st2,ed1,ed2;

        st1=st2=ed1=ed2=1;

        long long sum=0;

        int j=1;

        for(int i=1;i<=n&&j<=n;i++){

            if(i==1){

                qd[1].index=1;

                qd[1].v=a[1];

                qx[1].index=1;

                qx[1].v=a[1];

            }

            else{

                ed1=maxc(st1,ed1,a[i]); //二分找出d入队列的为止，维护最大值

                qd[ed1].v=a[i];

                qd[ed1].index=i;

                ed2=minc(st2,ed2,a[i]); //二分找出d入队列的为止，维护最小值

                qx[ed2].v=a[i];

                qx[ed2].index=i;

                while(qd[st1].v-qx[st2].v>=k&&st1<=ed1&&st2<=ed2)//计数

                {

                    if(qd[st1].index==j) st1++;

                    if(qx[st2].index==j) st2++;

                    sum+=(i-j);

                    j++;

                }

            }

        }

        while(j<=n) {

            sum+=(n-j+1);

            j++;

        }

        printf("%I64d\n",sum);

    }

}