刚看题的时候想维护一个分段函数想了好久，最后发现实在是伤身体，看完sol的第一句话我就发现我是sb
考虑分治，每次找到分值区间的某一个最大值的位置，枚举合法区间的左端点，同时确定区间的右端点的范围，处理完成后分治下去求解子区间
防止复杂度退化成(O(n^2))我们可以借鉴启发式合并的思想，每次枚举左端点的时候从长度较小的子区间里枚举，这样的最坏复杂的就是(O(nlogn))的（你从后往前看其实就是个启发式合并的过程）.用st表预处理区间最大值的位置
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,k,pos[300300],a[300300],L[300300],R[300300],maxp[300300][20],low[300300];
ll ans=0;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int query(int l,int r)
{
int p=low[r-l+1];
//cout << "query " << l << " " << r << " " << p << endl;
//cout << l << " " << r-(1<<p)+1 << endl;
int x1=maxp[l][p],x2=maxp[r-(1<<p)+1][p];
if (a[x1]>a[x2]) return x1;else return x2;
}
void solve(int l,int r)
{
if (r<l) return;
int pos=query(l,r),minlen=a[pos]-k;
//cout << l << " " << r << " " << pos << endl;
//system("pause");
if (pos-l<r-pos)
{
rep(i,l,pos)
{
int nowl=max(i+minlen-1,pos),nowr=min(r,R[i]);
if (nowr>=nowl) ans+=(nowr-nowl+1);
}
}
else
{
rep(i,pos,r)
{
int nowl=max(l,L[i]),nowr=min(i-minlen+1,pos);
if (nowr>=nowl) ans+=(nowr-nowl+1);
}
}
solve(l,pos-1);solve(pos+1,r);
}
int main()
{
int T=read();
while (T--)
{
n=read();k=read();
rep(i,1,n) {a[i]=read();maxp[i][0]=i;}
for (int p=1;(1<<p)<=n;p++)
for (int i=1;i+(1<<p)-1<=n;i++)
{
int l=maxp[i][p-1],r=maxp[i+(1<<(p-1))][p-1];
if (a[l]>a[r]) maxp[i][p]=l;else maxp[i][p]=r;
}
low[1]=0;rep(i,2,n) low[i]=low[i>>1]+1;
rep(i,1,n) pos[i]=0;
rep(i,1,n)
{
L[i]=pos[a[i]]+1;
pos[a[i]]=i;
}
rep(i,2,n) L[i]=max(L[i],L[i-1]);
rep(i,1,n) pos[i]=n+1;
per(i,n,1)
{
R[i]=pos[a[i]]-1;
pos[a[i]]=i;
}
per(i,n-1,1) R[i]=min(R[i],R[i+1]);
ans=0;
//rep(i,1,n) cout << L[i] << " " << R[i] << endl;
solve(1,n);
printf("%lld
",ans);
}
return 0;
}