题意:有一长度为\(n\)的数组,问有多少子数组的最大值和最小值之差大于\(k\).

题意:看数据范围,这题比较稳的写法应该是\(O(n)\),考虑一个区间,如果当前区间的最大值最小值之差已经大于\(k\)了,那么我们再去移动右区间也一定是合法的,也就是没有意义的,那么此时固定左区间,右贡献为\(n-r+1\),之后我们再去移动左区间直到不合法为止,理解的关键点在于不合法的时候移动右区间,为什么不是移动左区间呢?废话,因为移动左区间的话区间在变小,也就是元素越来越少,你本来大的区间都不合法,小区间还想合法?具体实现就是两个单调队列记录最大值和最小值然后双指针维护区间.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,m,k;
int a[N];
int q1[N],q2[N];

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    rep(i,1,n) cin>>a[i];
    while(m--){
        cin>>k;
        int i=1;
        int hh1=0,tt1=-1,hh2=0,tt2=-1;
        ll ans=0;
        rep(j,1,n){
            while(hh1<=tt1 && a[q1[tt1]]>=a[j]) tt1--;
            while(hh2<=tt2 && a[q2[tt2]]<=a[j]) tt2--;
            q1[++tt1]=j;
            q2[++tt2]=j;
            while(a[q2[hh2]]-a[q1[hh1]]>k){
                i++;
                if(q1[hh1]<i) hh1++;
                if(q2[hh2]<i) hh2++;
                ans+=n-j+1;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}