AT_abc444_e 题解

Moya_Rao · 2026-02-10 14:18:18 · 题解

双指针大法好，耶。

注意到若区间 [l,r] 满足条件，那么区间 [l+1,r],[l,r-1] 肯定也满足条件；若区间 [l,r] 不满足条件，那么区间 [l-1,r],[l,r+1] 肯定也不满足条件。这种单调性质启发我们用双指针解决问题。

升序枚举右端点 r 并考虑将其插入区间，找到第一个满足条件的左端点 l。双指针，不断让 l 向 r 靠近，只要现在的区间情况插入 r 无法合法，就删除 l 并让 l \gets l+1。最终得到第一个能使 r 合法的 l 后跳出循环，针对这个 r 累加 r-l+1 种左端点，即多了 r-l+1 种不同的区间。

思路没毛病，但是有一个问题，如何判断当前的区间情况插入 r 是不合法的呢？可以用 set 维护，但是数列中可能有重复元素，因此改用 multiset。只要在 multiset 内第一个不大于 a_r 的值 val_0 > a_r-D，或者第一个不小于 a_r 的值 val_1 < a_r + D，当前的状态对于新增下标 r 就肯定不合法。

判断的时候，因为总是要处理边界情况，做两次二分有些麻烦还容易出错，这里提供一种另外的方案：你只需要判断 multiset 内第一个不小于 a_r - D +1 的值 val_2 与 a_r + D - 1 的大小关系——即，若 val_2 > a_r + D - 1，那么 r 合法，否则不合法。这样可以使代码看起来更简洁。

于是这道题就结束啦。噢对了，记得要开 long long 喔！

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 4e5+5;
LL n,D,a[N],Ans;
multiset<LL> st;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    n=read(),D=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int l=1,r=1;r<=n;r++){
        while(!st.empty()){
            auto it=st.lower_bound(a[r]-D+1);
            if(it==st.end()||(*it)>a[r]+D-1)break;
            st.erase(st.find(a[l]));l++;
        }st.insert(a[r]),Ans+=r-l+1;
    }cout<<Ans<<"\n";
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！