RT，这个代码除了那几个memset，其他的地方时间复杂度都是对的。但是就是因此TLE了，想知道有没有什么好的解决方案。

code：

#include<bits/stdc++.h>
#define int long long
#define QwQ puts("QwQ")
#define ls now<<1
#define rs now<<1|1
using namespace std;
const int N=500005,M=400005;
int t,n,k,a[N],mp[N],dp[N],mn[M],sum[M];
inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		ans=(ans<<3)+(ans<<1)+(c^48);
		c=getchar();
	}
	return ans*f;
}
inline void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int query1(int now,int l,int r,int ql,int qr)
{
	if(l>=ql&&r<=qr) return mn[now];
	int mid=l+r>>1,res=1e9;
	if(ql<=mid) res=min(res,query1(ls,l,mid,ql,qr));
	if(qr>mid) res=min(res,query1(rs,mid+1,r,ql,qr));
	return res;
}
int query2(int now,int l,int r,int ql,int qr)
{
	if(l>=ql&&r<=qr) return sum[now];
	int mid=l+r>>1,res=0;
	if(ql<=mid) res+=query2(ls,l,mid,ql,qr);
	if(qr>mid) res+=query2(rs,mid+1,r,ql,qr);
	return res;
}
void update(int now,int l,int r,int x,int y)
{
	if(l==r)
	{
		mn[now]=min(mn[now],y);
		sum[now]++;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) update(ls,l,mid,x,y);
	else update(rs,mid+1,r,x,y);
	mn[now]=min(mn[ls],mn[rs]);
	sum[now]=sum[ls]+sum[rs];
	return;
}
signed main()
{
	t=read();
	while(t--)
	{
		int ans=0;
		n=read(),k=read();
		for(int i=1;i<=n;i++)
		{
			a[i]=read();
			mp[a[i]]++;
		}
		for(int i=1;i<=n;i++)
		{
			ans+=mp[a[i]]*(mp[a[i]]+1)/2;
			mp[a[i]]=0;
			dp[i]=0;
		}
		memset(mn,0x3f,sizeof(mn));
		memset(sum,0,sizeof(sum));
		for(int i=n;i>=1;i--)
		{
			int u=query1(1,1,1e5,a[i]+1,a[i]+k);
			if(u>=1e9) u=0;
			dp[i]=dp[u]+query2(1,1,1e5,a[i]+1,a[u]);
			update(1,1,1e5,a[i],i);
			ans+=dp[i];
		}
		reverse(a+1,a+n+1);
		memset(mn,0x3f,sizeof(mn));
		memset(sum,0,sizeof(sum));
		for(int i=n;i>=1;i--)
		{
			dp[i]=0;
			int u=query1(1,1,1e5,a[i]+1,a[i]+k);
			if(u==1e9) u=0;
			dp[i]=dp[u]+query2(1,1,1e5,a[i]+1,a[u]);
			update(1,1,1e5,a[i],i);
			ans+=dp[i];
		}
		write(ans);
		puts("");
	}
	return 0;
}