C题 滑动窗口

借鉴了KryptonAu大佬的代码，我只是复述

...

l, r分别为左端点和右端点，左端点l 刚开始为1，然后枚举右端点r

Max, Min分别为区间 [l,r] 的最大值和最小值

pos_max, pos_min分别为区间 [l,r] 离右端点r 最近的最大值和最小值的位置

当 Max-Min>k 时，当前的值一定是最大值或最小值

如果是最大值，则最小值太小，左端点l 需要增加到使得区间[l,r]内 Max-Min<=k

则从右端点r 到pos_min+1 的负循环中寻找左端点l，反之最小值一样

当 Max-Min=k 时，固定右端点r，区间[l,min(pos_max,pos_min)]的长度就是对答案的贡献

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll n,k,a[N],l=1,Max,Min,pos_max,pos_min,ans;

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int r=1;r<=n;r++){
        if(a[r]<=Min) Min=a[r],pos_min=r;
        if(a[r]>=Max) Max=a[r],pos_max=r;

        if(Max-Min>k){
            if(a[r]==Max){
                l=pos_min+1;
                Min=a[r],pos_min=r;
                for(int i=r;i>=l;i--){
                    if(Max-a[i]>k){
                        l=i+1;
                        break;
                    }
                    if(a[i]<Min) Min=a[i],pos_min=i;
                }
            }
            else if(a[r]==Min){
                l=pos_max+1;
                Max=a[r],pos_max=r;
                for(int i=r;i>=l;i--){
                    if(a[i]-Min>k){
                        l=i+1;
                        break;
                    }
                    if(a[i]>Max) Max=a[i],pos_max=i;
                }
            }
        }
        if(Max-Min==k) ans+=min(pos_max,pos_min)-l+1;
    }
    cout<<ans;
}