https://vjudge.csgrandeur.cn/problem/HDU-5289

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f,g,len,k;
long long anss;
int s[100005],ssss[100005][30],sssss[100005][30];
int erf(int l,int r){//二分 
	int mid;
	while(l<=r){
		mid=(l+r)/2;
		len=log2(r-l+1);
		long long ls=max(ssss[l][len],ssss[r+1-(1<<len)][len])-min(sssss[l][len],sssss[r+1-(1<<len)][len]);
		if(ls>k){
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	return l;
}
int main(){
	scanf("%lld",&g);
	for(int il=1;il<=g;il++){
		scanf("%lld",&a);
		scanf("%lld",&k);
		for(int i=1;i<=a;i++){
			scanf("%lld",&s[i]);
		}
		for(int j=0;(1 << j) <= a;j++){
			for(int i=1;i<=a - (1 << j) + 1;i++){
				if(j==0){
					ssss[i][0]=s[i];
					sssss[i][0]=s[i];
				}
				else{
					ssss[i][j]=max(ssss[i][j-1],ssss[i+(1 << (j - 1))][j-1]);
					sssss[i][j]=min(sssss[i][j-1],sssss[i+(1 << (j - 1))][j-1]);
				}
			}
		}	
		for(int i=1;i<=a;i++){
			anss=anss+erf(i,a)-i;
		}
		printf("%lld\n",anss);
		anss=0;
	}
	return 0;
}