Original proposer: admin

This problem can be solved with the sliding window technique.

When \(L\) is fixed

When \(L\) is fixed, let us consider the criteria for \(R\) to satisfy the condition.

If \((L, R)\) does not satisfy the condition, then there exists \(i\) and \(j\) such that \(L\leq i < j \leq R\) and \(|A_i-A_j|<D\). Due to this \((i,j)\), no pair \((L,R+\alpha)\) for \(\alpha \geq 1\) satisfies the condition.

That is, there exists \(f(L)\) such that \((L,L),(L,L+1),\dots,(L,f(L))\) satisfy the condition, while \((L,f(L)+1),\dots,(L,N)\) do not.

Finding \(F(L)\) for all $L

When \(f(L)\) is known, consider how to find \(f(L+1)\). Since \((L,f(L))\) satisfies the condition, so does \((L+1,f(L))\) because we have less constraint pairs. Thus, \(f(L)\leq f(L+1)\), and it is sufficient to “resume” from \(f(L)\) to find \(f(L+1)\). Therefore, we can execute a sliding-window algorithm as shown in the following pseudocode.

Pseudocode

ans = 0
R = 1
for L in 1..N:
  while (L, R) satisfies the condition:
    R <- R+1
  //(L,L),...(L,R-1) satisfy the condition
  ans <- ans+(R-L)

Solving the decision problem fast

For this algorithm to run fast, we need to decide fast if \((L,R)\) satisfies the condition.

When \((L,R-1)\) satisfies the condition, \((L,R)\) satisfies the condition if and only if \(|A_i-A_R| \geq D\) for all \(L \leq i < R\). This is equivalent to “the minimum value among \(A_L,\dots,A_{R-1}\) greater than or equal to \(A_R\) is \(A_R+D\) or greater, and the maximum value among them less than or equal to \(A_R\) is \(A_R-D\) or less.”

Therefore, it is sufficient to have a data structure that supports:

• insertion of an element
• deletion of an element
• retrieval of the minimum element greater than or equal to \(x\)
• retrieval of the maximum element less than or equal to \(x\)

The order set supports these operations in \(O(\log N)\) time, so the problem has been solved in a total of \(O(N\log N)\) time.

Sample code (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;
}