题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$L$，$R(1 \leq L \leq R \leq 10^9)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

输出有多少对$(i, j)$满足$i \lt j$且$L \leq a[i] + a[j] \leq R$。

输入样例

4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1

输出样例

2
7
0
1

算法

二分查找

做完之后感觉好像可以用双指针，但就算用双指针也需要先对数组排序，并不影响整体的时间复杂度，所以还是不写了。

依题意很容易认识到一点“$i$和$j$谁是谁根本无所谓”，所以为了更方便，直接对数组先排个序，然后枚举那个较小值，假设为$a[i]$。对于每个$a[i]$，在它右边二分查找到第一个满足$a[i]+a[r] \gt R$的位置$r$，以及第一个满足$a[i]+a[l] \geq L$的位置$l$，所有$j \in [l,r)$的元素$a[j]$都满足$a[i]+a[j] \in [L,R]$，能够贡献$r-l$个数对，把所有$i$的贡献累加起来就是答案。

复杂度分析

时间复杂度

排序的时间复杂度为$O(nlog_2n)$。枚举$i$的时间复杂度为$O(n)$，对每个$i$二分查找范围的时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了排序之外只使用了有限几个变量，而以快速排序为基准，额外空间复杂度为$O(log_2n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010;
int t, n, L, R, a[N];

void solve() {
    sort(a + 1, a + n + 1);
    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        int l = lower_bound(a + i + 1, a + n + 1, L - a[i]) - a;
        int r = upper_bound(a + i + 1, a + n + 1, R - a[i]) - a;
        ans += r - l;
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d%d", &n, &L, &R);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        solve();
    }
    return 0;
}