NOTE
比赛链接：Codeforces Round 995 (Div. 3)

D - Counting Pairs#

关键词：二分

思路#

题目要求找出一对下标 $(i, j)$ ，满足 $1 \le i < j \le n$ ，且在删去这两个数后，剩余元素的和在 $[x, y]$ 之间。

假设整个数组所有元素的总和为 $S$ 。如果我们删去 $a_i$ 和 $a_j$ ，剩余元素的和就是 $S - (a_i + a_j)$ 。

根据题意，我们需要满足： $x \le S - (a_i + a_j) \le y$

我们对这个不等式进行移项，把未知的 $a_i + a_j$ 提取出来：

先两边减去 $S$ ：

$x - S \le -(a_i + a_j) \le y - S$
两边同时乘 $-1$ ：

$S - y \le a_i + a_j \le S - x$

令 $L = S - y$ ， $R = S - x$ 。现在，问题就转换成了：在一个数组中，寻找有多少对元素的和落在给定的区间 $[L, R]$ 内。

枚举每一个元素 $a_i$ ，对于当前元素 $a_i$ ，我们需要在它之后的元素中找出有多少个元素 $a_j$ 满足 $L - a_i \le a_j \le R - a_i$ ，先排序，后用二分查找即可。

NOTE
注意 std::accumulate 的返回值和累加过程的类型取决于第三个参数，所以应该传 0LL。

Code#

1
// Problem: CF 2051 D
2
// Contest: Codeforces - Codeforces Round 995 (Div. 3)
3
// URL: https://codeforces.com/contest/2051/problem/D
4
// Time: 2026-05-17 23:27:47
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 2e5 + 10;
25

26
ll a[N];
27

28
void solve()
29
{
30
    ll n, x, y;
31
    cin >> n >> x >> y;
32

33
    for (int i = 1; i <= n; i++)
34
        cin >> a[i];
35

36
    ll sum = accumulate(a + 1, a + n + 1, 0LL);
37

38
    sort(a + 1, a + n + 1);
39

40
    ll res = 0;
41
    for (int i = 1; i <= n; i++)
42
    {
43
        ll pos1 = lower_bound(a + i + 1, a + n + 1, sum - a[i] - y) - a;
44
        ll pos2 = upper_bound(a + i + 1, a + n + 1, sum - a[i] - x) - a - 1;
45

46
        if (pos1 <= pos2)
47
            res += pos2 - pos1 + 1;
48
    }
49

50
    cout << res << endl;
51
}
52

53
int main()
54
{
55
    fastio();
56

57
    int T = 1;
58
    cin >> T;
59

60
    while (T--)
61
        solve();
62

63
    return 0;
64
}