原案：admin

この問題は尺取法により解くことができます。

\(L\) を固定した問題

\(L\) を固定したとき、どのような \(R\) が条件を満たすか考えます。

もし \((L,R)\) が条件を満たさないなら、ある \(i,j\) が存在して、\(L\leq i < j \leq R\) かつ \(|A_i-A_j|<D\) となります。この \((i,j)\) が反例となり、どのような\(\alpha \geq 1\) に対しても \((L,R+\alpha)\) は条件を満たしません。

すなわち、ある \(f(L)\) が存在し、\((L,L),(L,L+1),\dots,(L,f(L))\) は条件を満たし、\((L,f(L)+1),\dots,(L,N)\) は条件を満たさないことになります。

全ての \(L\) での \(f(L)\) を求める

\(f(L)\) がわかっているとき \(f(L+1)\) を求めることを考えます。\((L,f(L))\) が条件を満たすため、そこから対象となる組が減った \((L+1,f(L))\) も条件を満たします。即ち \(f(L)\leq f(L+1)\) であり、\(f(L+1)\) を求めるには \(f(L)\) の”続き”から確認をすれば十分です。よって、以下の擬似コードに示すような尺取法を行うことができます。

擬似コード

ans = 0
R = 1
for L in 1..N:
  while (L, R) が条件を満たす:
    R <- R+1
  //(L,L),...(L,R-1)が条件を満たす
  ans <- ans+(R-L)

判定問題を高速に解く

この尺取法が高速に動作するためには、判定問題「\((L,R)\) が条件を満たすか？」を高速に判定する必要があります。

\((L,R-1)\) が条件を満たすとき、\((L,R)\) が条件を満たすための必要十分条件は、全ての \(L \leq i < R\) に対して \(|A_i-A_R| \geq D\) となることです。このことは「\(A_L,\dots,A_{R-1}\) のうち \(A_R\) 以上の最小の要素が \(A_R+D\) 以上かつ、\(A_R\) 以下の最大の要素が \(A_R-D\) 以下であること」と同値です。

よって、以下ができるデータ構造があれば十分です

• 要素の追加
• 要素の削除
• \(x\) 以上の最小の要素の取得
• \(x\) 以下の最大の要素の取得

これらは ordered set を用いることでいずれも \(O(\log N)\) 時間で行えるため、\(O(N\log N)\) でこの問題が解けました。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
	int n,d;
	cin >> n >> d;
	vector<int>a(n);
	for(auto&x:a)cin >> x;
	
	ll ans=0;
	set<ll>s({(ll)-1e9,(ll)2e9});
	int r=0;
	for(int l=0;l<n;l++){
		while(r<n){
			auto it=s.lower_bound(a[r]);
			if(*it-a[r]<d)break;
			it--;
			if(a[r]-*it<d)break;
			s.insert(a[r]);
			r++;
		}
		ans+=r-l;
		s.erase(a[l]);
	}
	cout << ans << endl;
}