#include <stdio.h> #include <stdlib.h> //#include <math.h> typedef long long ll; #define Max 100010 #define fMax(a,b) (a>b?a:b) #define fMin(a,b) (a<b?a:b) int a[Max]; int max[Max]; int min[Max]; int Nmax; int Nmin; void build(int dx,int begin,int end){ if(begin==end){ max[dx] = min[dx] = a[begin]; return; } int m = (begin+end)/2; build(dx*2,begin,m); build(dx*2+1,m+1,end); max[dx] = fMax(max[dx*2],max[dx*2+1]); min[dx] = fMin(min[dx*2],min[dx*2+1]); } /*void find(int dx,int begin,int end){ if(begin>=end) return; Nmax = fMax(Nmax,max[dx]); Nmin = fMin(Nmin,min[dx]); int m = (begin+end)/2; find(dx*2,begin,m); find(dx*2+1,m+1,end); }*/ void search(int dx,int begin,int end,int i,int j){ if(j<begin||i>end) return; if(begin>=i&&end<=j){ Nmax = fMax(Nmax,max[dx]); Nmin = fMin(Nmin,min[dx]); return; } int m=(begin+end)/2; search(dx*2,begin,m,i,j); search(dx*2+1,m+1,end,i,j); } int main() { int T; scanf("%d",&T); while(T--){ int n,k; //ll sum = 0; scanf("%d%d",&n,&k); int i,j; ll sum = 0; for(i=1;i<=n;i++) scanf("%d",a+i); build(1,1,n); for(i=1;i<=n;i++){ Nmax = -1; Nmin = 9999999; search(1,1,n,i,n); if(Nmax-Nmin<k) sum += n-i+1; else{ // printf("jaja\n"); Nmax = Nmin = a[i]; for(j=i;j<n;j++){ if(Nmax-Nmin>=k) break; Nmax = fMax(Nmax,a[j+1]); Nmin = fMin(Nmin,a[j+1]); sum++; } } // printf("sum=%lld\n",sum); } printf("%lld\n",sum); // printf("max=%d\n",fMax(100,2)); } //printf("Hello world!\n"); return 0; } |
Double click to view unformatted code.