C-小y的序列

滑动窗口

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define ll long long
#define inf 1000000002
#define endl '\n'
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const double pi = acos(-1);
const int maxn = 1e6+7;

int n,k;
int arr[maxn];
int MIN = inf;
int MAX = -inf;
int l=1;
int r;
int pos_max,pos_min;
ll ans;

int main(){
    IOS;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(r = 1;r<=n;r++){
        if(MAX<=arr[r]) MAX = arr[r],pos_max = r;
        if(MIN>=arr[r]) MIN = arr[r],pos_min = r;
        if(MAX - MIN >k){
            if(arr[r] == MAX){
                l = pos_min+1,MIN=arr[r],pos_min=r;
                for(int yyh = r;yyh>=l;yyh--){
                    if(MAX - arr[yyh]>k){
                        l = yyh+1;
                        break;
                    }
                    if(arr[yyh]<MIN) MIN=arr[yyh],pos_min=yyh;
                }
            }
            else if(arr[r] == MIN){
                l = pos_max+1,MAX=arr[r],pos_max=r;
                for(int yyh = r;yyh>=l;yyh--){
                    if(arr[yyh]-MIN>k){
                        l = yyh+1;
                        break;
                    }
                    if(arr[yyh]>MAX) MAX=arr[yyh],pos_max=yyh;
                }
            }
        }
        if(MAX-MIN==k) ans+=min(pos_min,pos_max)-l+1;
    }
    cout<<ans<<endl;
}