Input In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means the maximum difference between abilities of staff in a group is less than k. The second line contains n integers:a[1],a[2],…,a[n](0<=a[i]<=10^9),indicate the i-th staff’s ability.
Output For each test,output the number of groups.
Sample Input 2 4 2 3 1 2 4 10 5 0 3 4 5 2 1 6 7 8 9
Sample Output 5 28
#include <cstdio> #include <map> #include <iostream> #include<cstring> #include<bits/stdc++.h> #define ll long long int #define M 6 using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; int a[100007]; int maxn[100007][20],minn[100007][20]; void preST(int n){ for(int i=1;i<=n;i++){ maxn[i][0]=a[i]; minn[i][0]=a[i]; } int m=log(n)/log(2)+1; for(int j=1;j<m;j++) for(int i=1;i<=(n-(1<<j)+1);i++){ maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]); minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]); } } int queryST1(int l,int r){ int k=log(r-l+1)/log(2); return max(maxn[l][k],maxn[r-(1<<k)+1][k]); } int queryST2(int l,int r){ int k=log(r-l+1)/log(2); return min(minn[l][k],minn[r-(1<<k)+1][k]); } int main(){ //ios::sync_with_stdio(false); int t; scanf("%d",&t); while(t--){ int n,k; scanf("%d%d",&n,&k);; for(int i=1;i<=n;i++) scanf("%d",&a[i]);; preST(n); ll ans=0; int l,r; for(int i=1;i<=n;i++){ int pos; l=i; r=n; while(l<=r){ int mid=(l+r)>>1; int mm=queryST1(i,mid); int nn=queryST2(i,mid); if(mm-nn<k){ l=mid+1; pos=mid; } else r=mid-1; } ans+=(l-i); } printf("%lld\n",ans); } }