E - Sparse Range 题解

豆包翻译。

简单来说： 给定整数数组a和整数d，统计数组中所有满足以下条件的连续子数组的数量：
子数组中任意两个元素的差的绝对值都大于等于d。

数组长度 n 的范围：1 ≤ n ≤ 4 × 10^5 整数 d 的范围：1 ≤ d ≤ 10^9

最朴素的想法，我们o(n^2 )枚举左右端点，然后o(n)判断，显然o(n^3)超时。

如何优化？ -> 滑动窗口+set维护。
固定左端点 L，尽可能向右扩展 R 直到窗口不满足条件，确保找到最远的合法边界。

对于每个 L，以 L 为左端点的合法子数组数量为 R-L，累加得到总数。

注意到我们R指针是不会回退的，因为满足单调性。

具体地，当我们区间[L,R]判断完毕后，我们移动L，[L+1,R]必然合法，因为判断条件变少，我们的目的是让R尽可能大，即从R+1开始，不用回退。
这个性质让我们的时间复杂度大大降低。

于是我们想想怎么判断区间是否合法。

显然用set.

每次我们拓展右端点，只需比较原来set中的前驱和后继。为什么？ 因为我们只关心与新插入的元素相邻的位置即可，若满足，则该区间必然合法。

思路变得愈发清晰。

万事具备，只欠代码~

#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;
}   来自ATCODER题解代码

谢谢观看。