小y的序列（ST表&二分）---牛客练习赛96-C

牛客练习赛96-小y的序列

解析

ST表预处理区间极值差

可以发现，对于一个区间 [ l , r ] [l,r] [l,r]，其极值差存在单调不减的性质，当我们区间在右侧添加一个值 x x x 时，此时最小值不变或减小，最大值不变或增大，所以总区间的极值差不减。

对于每一个 i i i，固定其为左端点，然后在 [ i , n ] [i,n] [i,n] 二分右端点，找到恰好满足 M a x − M i n = k Max-Min = k Max−Min=k 的那一段区间

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
const int N=1e6+5;

int n,k;
int a[N],maxx[N][21],minn[N][21];

void init(){
	for(int i=1;i<=n;i++){
		maxx[i][0]=a[i];
		minn[i][0]=a[i];
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]);
			minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
		}
	}
}
int check(int l,int r){
	int k=log2(r-l+1);
	return max(maxx[l][k],maxx[r-(1<<k)+1][k])-min(minn[l][k],minn[r-(1<<k)+1][k]);
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	init();
	long long ans=0;
	for(int i=1;i<=n;i++){
		int l=i,r=n+1;
		while(l<r){
			int mid=l+r>>1;
			if(check(i,mid)>=k) r=mid;
			else l=mid+1;
		}
		ans-=l;
		l=i,r=n+1;
		while(l<r){
			int mid=l+r>>1;
			if(check(i,mid)>k) r=mid;
			else l=mid+1;
		}
		ans+=l;
	}
	cout<<ans;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt=1;
//	cin>>tt;
	while(tt--) solve();
	return 0;
}