hdu5289 单调队列

这题说的是给了 n个数 然后让你计算出所有区间中那些数的最大值减最小值小于k这样的区间有多少个

/*

  这样我们给我们在处理过程中的区间做一些处理

  我们在处理即将进来的数的时候我们并不知道他是不是我们区间的最小或者最大值

  但是我们可以将他们处理一下 用两个队列 一个队列放的逐渐减小的数列

  一个放的是逐渐增大的队列，放的位置必须按照出现的位置来放，按照大小来放，

  把一些没用的点排除了，因为他们没有存在的必要《即不能当最大值也不能当最小值》

  一但出现了大于k的情况我们可以判断现在的维护的这个队列的区间大小来得到结果

*/

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#include<iostream>

using namespace std ;

#define LL __int64

int a[];

int main()

{

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; cc++)

        {

            deque<int>d1,d2;

            int n,k;

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

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

                {

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

                }

            long long ans=;

            int l=;

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

                {

                    while(!d1.empty()&&d1.back()<a[i])d1.pop_back();

                    d1.push_back(a[i]);

                    while(!d2.empty()&&d2.back()>a[i])d2.pop_back();

                    d2.push_back(a[i]);

                    while(!d1.empty()&&!d2.empty()&&d1.front()-d2.front()>=k)

                        {

                            ans+=i-l;

                            if(d1.front()==a[l])d1.pop_front();

                            if(d2.front()==a[l])d2.pop_front();

                            l++;

                        }

                }

            while(l<n){

                ans+=n-l;l++;

            }

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

        }

    return ;

}