ABC444_E
问题陈述
给你一个长度为 N , (A1,…,AN) 和一个正整数 D 的整数序列。
求满足以下两个条件的整数对 (L,R) 的个数：
- 1≤L≤R≤N
- (AL,AL+1,…,AR) 中任意两个元素的差至少为 D 。
- 即 ∣Ai−Aj∣≥D 满足 L≤i<j≤R 的所有整数对 (i,j) 。
这道题考虑用双指针来做
我们考虑固定一个 \(r\) ，向找到能达到的最小 \(l\) ，那对于一对 \(l,r\) 的贡献就是 \(r-l+1\) ，考虑差值是否合法
不合法：考虑把 \(l\) 不断向右移动，，找到每一个 \(r\) 合法的 \(l\) ，计算答案即可
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+10;
const int INF=1e9;
int n,a[N],d;
multiset<int> s;
int main(){cin>>n>>d;for(int i=1;i<=n;i++){cin>>a[i];}ll ans=0;for(int l=1,r=1;r<=n;r++){auto p=s.insert(a[r]);while(p!=s.begin()&&(*p)-(*prev(p))<d||p!=--s.end()&&(*next(p))-(*p)<d){s.erase(s.find(a[l]));l++;}ans+=r-l+1;}cout<<ans<<endl;return 0;
}