题目描述

难度分:$1300$

输入$n(1 \leq n \leq 10^5)$，$d(1 \leq d \leq 10^9)$和长为$n$的严格递增数组 $a(-10^9 \leq a[i] \leq 10^9)$。

输出有多少个三元组$(i,j,k)$满足$i \lt j \lt k$且$a[k]-a[i] \leq d$。

输入样例$1$

4 3
1 2 3 4

输出样例$1$

4

输入样例$2$

4 2
-3 -2 -1 0

输出样例$2$

2

输入样例$3$

5 19
1 10 20 30 50

输出样例$3$

1

算法

前缀和+二分

刚开始没注意到$a$是单调递增的，用了树状数组，麻烦得要死，后来注意到$a$是有序的就简单多了。

枚举三元组的第一个元素$i$，然后在$[i+2,n]$上二分找到最后一个满足$a[k]-a[i] \leq d$的$k$，此时$[i+2,k]$中的所有元素都可以作为三元组的第三个元素。那$(i,k)$中的所有元素就可以作为三元组的第二个元素$j$，对于给定的$i$，$j$的个数应该为$\Sigma_{index=i+2}^{k}(index-i-1)=\Sigma_{index=i+2}^{k}index-(k-i-1) \times (i+1)$，预处理一个下标的前缀和数组就能$O(1)$计算这个贡献。

复杂度分析

时间复杂度

预处理下标的前缀和数组时间复杂度为$O(n)$，枚举$i$的时间复杂度为$O(n)$，对于给定的$i$，计算它的贡献需要进行二分，时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈主要在于下标的前缀和数组$s$，它的空间是线性的，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, d, a[N];
LL s[N];

int main() {
    scanf("%d%d", &n, &d);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + i;
    }
    LL ans = 0;
    for(int i = 1; i <= n - 2; i++) {
        int j = upper_bound(a + i + 2, a + n + 1, a[i] + d) - a;
        j--;
        // [i+2,j]都可以
        if(j >= i + 2) {
            LL cnt = j - i - 1;
            ans += s[j] - s[i + 1] - cnt*(i + 1);
        }
    }
    printf("%lld\n", ans);
    return 0;
}