豆包翻译。
简单来说： 给定整数数组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题解代码
谢谢观看。