Counting Pairs
Contest: Codeforces Round 995 (Div. 3)
Difficulty rating: 1200
Tags: binary search, sortings, two pointers

You are given a sequence $$$a$$$, consisting of $$$n$$$ integers, where the $$$i$$$-th element of the sequence is equal to $$$a_i$$$. You are also given two integers $$$x$$$ and $$$y$$$ ($$$x \le y$$$).

A pair of integers $$$(i, j)$$$ is considered interesting if the following conditions are met:

- $$$1 \le i < j \le n$$$;
- if you simultaneously remove the elements at positions $$$i$$$ and $$$j$$$ from the sequence $$$a$$$, the sum of the remaining elements is at least $$$x$$$ and at most $$$y$$$.

Your task is to determine the number of interesting pairs of integers for the given sequence $$$a$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines:

- The first line contains three integers $$$n, x, y$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le x \le y \le 2 \cdot 10^{14}$$$);
- The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$).

Additional constraint on the input: the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output one integer — the number of interesting pairs of integers for the given sequence $$$a$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, there are $$$4$$$ interesting pairs of integers:

1. $$$(1, 2)$$$;
2. $$$(1, 4)$$$;
3. $$$(2, 3)$$$;
4. $$$(3, 4)$$$.

Example input:
7
4 8 10
4 6 3 6
6 22 27
4 9 6 3 4 5
3 8 10
3 2 1
3 1 1
2 3 4
3 3 6
3 2 1
4 4 12
3 3 2 1
6 8 8
1 1 2 2 2 3

Example output:
4
7
0
0
1
5
6

Editorial:
There is a common trick in problems of the form "count something on segment $$$[l, r]$$$": calculate the answer for $$$[0, r]$$$, and then subtract the answer for $$$[0, l-1]$$$. We can use this trick in our problem as follows: calculate the number of pairs $$$i,j$$$ such that the sum of all other elements is less than $$$y+1$$$, and subtract the number of pairs such that the sum is less than $$$x$$$.
Now we need to solve the following problem: given an array and an integer $$$x$$$, calculate the number of ways to choose $$$i,j$$$ ($$$1 \le i < j \le n$$$) so that the sum of all elements, except for $$$a_i$$$ and $$$a_j$$$, is less than $$$x$$$.
Naive solution (iterate on the pair, calculate the sum of remaining elements) works in $$$O(n^3)$$$. It can be improved to $$$O(n^2)$$$ if, instead of calculating the sum of remaining elements in $$$O(n)$$$, we do it in $$$O(1)$$$: if we remove $$$a_i$$$ and $$$a_j$$$, the remaining elements sum up to $$$s - a_i - a_j$$$, where $$$s$$$ is the sum of all elements.
However, $$$O(n^2)$$$ is still too slow. For every $$$i$$$, let's try to calculate the number of elements $$$j$$$ which "match" it faster. If we sort the array, the answer won't change; but in a sorted array, for every $$$i$$$, all possible values of $$$j$$$ form a suffix of the array (if $$$s - a_i - a_j < x$$$ and $$$a_{j+1} \ge a_j$$$, then $$$s - a_i - a_{j+1} < x$$$).
So, for every $$$i$$$, let's find the minimum $$$j'$$$ such that $$$s - a_i - a_{j'} < x$$$; all $$$j \ge j'$$$ are possible "matches" for $$$i$$$. This can be done with two pointers method: when we decrease $$$i$$$, the index $$$j'$$$ won't decrease.
Unfortunately, this method has an issue. We need to calculate only pairs where $$$i<j$$$, but this method doesn't maintain this constraint. However, this issue can be easily resolved.
First, let's get rid of pairs where $$$i=j$$$. To do so, simply calculate the number of indices $$$i$$$ such that $$$s - 2a_i < x$$$.
Then, let's get rid of pairs where $$$i>j$$$. For every such pair, there is a pair with $$$i<j$$$ where these two indices are swapped (and vice versa), so we just need to divide the number of pairs by $$$2$$$.
Now we have a solution working in $$$O(n \log n)$$$ for each test case. Instead of two pointers, you can use binary search, the complexity will be the same.