CF 1762 F

SFlyer / 2024-09-24 / 原文

考虑怎么不重不漏的计算每一个区间。可以发现，每一个可行的区间一定是可以找到 $i_1\sim i_k$ 使 $a_{i_1}\sim a_{i_k}$ 是单调不增或者不降的。

这是因为，考虑有一个地方比两边都要小，那么我们可以直接忽略它，两边的差一定在 $k$ 以内。比两边都大同理。因此我们现在就要算单调不增个数加单调不降减去 $a_l=a_r$ 的 $[l,r]$ 个数。现在只讨论一种单调不降的。

考虑把序列转化成平面上的点，也即 $(i,a_i)$。

设 $f_r$ 为右端点为 $r$ 的方案数，先算出 $lst_r$ 为在左边第一个 $a_{i}\in [a_i-k,a_i]$ 的位置 $i$。则 $f_r$ 可以从 $f_{lst_r}$ 转移过来。上图这种情况下，如果我们想要算 $r=5$ 的答案，$lst_5=4$，所以 $f_5$ 有一部分是 $f_4$ 贡献的。但是容易发现 $(3,5)$ 这个点没有被算进去，因此还要加上前面 $a_i\in [a_{lst_r}+1,a_i]$ 的 $i$ 的个数。可以直接加，因为这个区间一定是可以一步到达的。

找 $lst_r$ 可以用线段树，后面的部分可以用树状数组。

时间复杂度 $\mathcal{O}(n\log n)$。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5e5+5;
const int A = 1e5+5;

int n,k,a[N],lu[N],ld[N],bit[A],f[N],m=A-5;

void M(int p,int v){
	while (p<A){
		bit[p]+=v,p+=p&-p;
	}
}

int Q(int p){
	int res=0;
	while (p){
		res+=bit[p],p-=p&-p; 
	}
	return res;
}

int S(int l,int r){
	return Q(r)-Q(l-1);
}

int t[N<<2];

void pu(int k){
	t[k]=max(t[k<<1],t[k<<1|1]);
}

void upd(int k,int l,int r,int p,int v){
	if (l==r){
		t[k]=v;
		return;
	}
	int mid=l+r>>1;
	if (p<=mid) upd(k<<1,l,mid,p,v);
	else upd(k<<1|1,mid+1,r,p,v);
	pu(k);
}

int qy(int k,int l,int r,int ql,int qr){
	if (ql<=l && r<=qr){
		return t[k];
	}
	if (r<ql || l>qr){
		return 0;
	}
	int mid=l+r>>1;
	return max(qy(k<<1,l,mid,ql,qr),qy(k<<1|1,mid+1,r,ql,qr));
}

void solve(){
	cin>>n>>k;
	map<int,ll> mp;
	for (int i=1; i<=n; i++){
		cin>>a[i];
		mp[a[i]]++;
	}
	for (int i=1; i<=n; i++){
		int l=max(1,a[i]-k),r=a[i];
		lu[i]=qy(1,1,m,l,r);
		l=a[i],r=min(m,a[i]+k);
		ld[i]=qy(1,1,m,l,r);
		upd(1,1,m,a[i],i);
	}
	for (int i=1; i<=n; i++){
		upd(1,1,m,a[i],0);
	}
	ll ans=0;
	for (int i=1; i<=n; i++){
		if (lu[i]==0){
			f[i]=1,ans++;
			M(a[i],1);
			continue;
		}
		f[i]=f[lu[i]]+S(a[lu[i]]+1,a[i])+1;
		ans+=f[i];
		M(a[i],1);
	}
	for (int i=1; i<=n; i++) M(a[i],-1);
	for (int i=1; i<=n; i++){
		if (ld[i]==0){
			f[i]=1,ans++;
			M(a[i],1);
			continue;
		}
		f[i]=f[ld[i]]+S(a[i],a[ld[i]]-1)+1;
		ans+=f[i];
		M(a[i],1);
	}
	for (int i=1; i<=n; i++) M(a[i],-1);
	for (auto u : mp){
		ll c=u.second;
		ans-=c*(c+1)/2;
	}
	cout<<ans<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin>>t;
	while (t--){
		solve();
	}
	return 0;
}