本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-28 11:09:43

思路

发现若合法子序列的三个连续元素 $x,y,z$ 满足 $a_x\ge a_y,a_y\le a_z$，那么一定有 $\left| a_z-a_x\right|\le k$，可以删掉中间的 $a_y$，$a_x\le a_y,a_y\ge a_z$ 的也一样。所以所有合法子序列均可通过删除操作变得单调不增或单调不降，因此只考虑单调序列即可。

显然单调不增和单调不降两种序列只会在 $a_l=a_r$ 时重复计算，因此分别计算后减去所有的重复贡献即可。可以先计算单调不增的区间数，然后进行 $a_i\leftarrow P-a_i+1$ 的转化（$P$ 为 $a_i$ 的值域），就把原来的单调不降变成了单调不增，再做一遍即可。

考虑怎么处理这个序列，发现对于 $i$ 后面第一个 $a_i\le a_j\le a_i+k$ 的 $j$，如果直接接上这个数，对于后面继续选不小于 $a_j$ 的数一定不劣。那么设 $f_i$ 表示 $l=i$ 时单调不增序列的结尾 $r$ 的个数，可以直接先把 $f_i$ 累加上 $f_j$。

剩下的就只有 $j$ 后面小于 $a_j$ 的数，这些数不能接在 $a_j$ 后面，需要另外统计。根据 $j$ 是第一个合法数的定义，$j$ 前面已经不可能有 $[a_i,a_j]$ 内的数，所以需要另外统计的个数等价于 $i$ 后面在 $[a_i,a_j)$ 范围内数的个数。

现在需要求的是每个数后面的 $j$（代码中为 $nxt_i$），考虑按照 $a$ 的值从大到小处理，用 set 维护目前在 $[x,x+k]$ 范围内的数，求 $nxt$ 时在 set 中二分即可，需要注意 $a$ 值相等的位置要从后往前加入 set，才能在前面计算时找到后面相等的数。另外还需要维护每个数后面在 $[a_i,a_{nxt_i})$ 内的数，这个在倒序处理时维护权值树状数组即可实现。

另外还需要注意所有的清空都需要清空每个 $a_i$ 的贡献，而不是对整个数组清空，否则时间复杂度是假的。

代码

#include<iostream>
#include<vector>
#include<set> 
#include<algorithm>
#define int long long
using namespace std;
const int N=5e5+10;
const int P=1e5;
int n,k,res,a[N],t[N],nxt[N],f[N];
set <int> pos;
vector <int> tp[N],tv; 
struct bit
{
	int b[N];
	int lowbit(int x){return x&(-x);}
	void add(int p,int x){for(;p<=P;p+=lowbit(p)) b[p]+=x;}
	int query(int p){int tr=0; for(;p;p-=lowbit(p)) tr+=b[p]; return tr;} 
}T;
void solv()
{
	for(int i=1;i<=n;i++)
	{
		if(tp[a[i]].empty()) tv.push_back(a[i]);
		tp[a[i]].push_back(i);
	}
	sort(tv.rbegin(),tv.rend()),pos.insert(n+1); int l=0;
	for(int x:tv)
	{
		while(tv[l]>x+k)
		{
			for(int p:tp[tv[l]]) pos.erase(p);
			l++; 
		}
		sort(tp[x].rbegin(),tp[x].rend());
		for(int p:tp[x]) nxt[p]=(*pos.lower_bound(p)),pos.insert(p);
	}
	for(int x:tv) tp[x].clear();
	tv.clear(),pos.clear();
	for(int i=n;i>=1;i--)
	{
		f[i]=1;
		if(nxt[i]!=n+1) f[i]=f[nxt[i]]+T.query(a[nxt[i]]-1)-T.query(a[i]-1)+1;
		T.add(a[i],1),res+=f[i];
	}
	for(int i=1;i<=n;i++) T.add(a[i],-1);
}
void sol()
{
	cin>>n>>k,res=0;
	for(int i=1;i<=n;i++) cin>>a[i],t[a[i]]++,res-=t[a[i]];
	solv();
	for(int i=1;i<=n;i++) t[a[i]]--,a[i]=P-a[i]+1;
	solv(),cout<<res<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TT; cin>>TT;
	while(TT--) sol();
	return 0;
}