View Code of Problem 3572

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define N 400222
int maxc[N][30],minc[N][30],a[N],n,m;
int ifmax(int a,int b)
{
        if(a>b)
                return a;
        return b;
}
int ifmin(int a,int b)
{
        if(a<b)
                return a;
        return b;
}
int logg(int x)
{
        int cnt=-1;
        while(x)
        {
                cnt++;
                x=x>>1;
        }
        return cnt;
}
void QWER()
{
        int i,j;
        for(i=1;i<=n;i++)
        {
                maxc[i][0]=a[i];
                minc[i][0]=a[i];
        }
        for(j=1;j<=logg(n);j++)
                for(i=1;i+(1<<j)-1<=n;i++)
        {
                maxc[i][j]=ifmax(maxc[i][j-1],maxc[i+(1<<(j-1))][j-1]);
                minc[i][j]=ifmin(minc[i][j-1],minc[i+(1<<(j-1))][j-1]);
        }
}
int kmp(int x,int y)
{
      int k=logg(y-x+1);
      return (ifmax(maxc[x][k],maxc[y+1-(1<<(k))][k])-ifmin(minc[x][k],minc[y+1-(1<<(k))][k]));
}
int main()
{
        //freopen("1002.in","r",stdin);
        int i,da,di,x,y,k,t;
        long long cnt;
        scanf("%d",&t);
        while(t--)
        {
                scanf("%d%d",&n,&m);
                for(i=1;i<=n;i++)
                        scanf("%d",&a[i]);
                QWER();
                k=1,cnt=0;
                for(i=1;i<=n;i++)
                {
                        while(kmp(k,i)>=m&&k<i)
                                k++;
                        cnt=cnt+(i-k+1);
                }
                printf("%lld\n",cnt);
        }
        return 0;
}