644. Pairs Whose Sum Lands In a Range
Given n integers and two bounds lower and upper, count the pairs of POSITIONS
i < j whose values add to something between the bounds, INCLUSIVE at both ends.
0 1 7 4 4 5, between 3 and 6 -> 6
1 7 9 2 5, between 11 and 11 -> 1
1 2 3, between 100 and 200 -> 0
## Turn a band into a difference of two counts
Counting pairs inside a band directly is awkward, because a pointer move can leave the band through either side. Counting pairs BELOW a ceiling is easy, and a band is the difference of two such counts:
answer = (pairs with sum <= upper) - (pairs with sum <= lower - 1)
One helper, called twice. Recognising that a range count is a difference of two boundary counts is worth much more than this problem alone: the same move turns a range question into two easier ones almost everywhere.
## Counting pairs at or below a ceiling
Sort, then sweep from both ends:
i = 0, j = n-1, c = 0
while i < j:
if a[i] + a[j] <= limit: c += j - i; i += 1
else: j -= 1
When the sum fits, every partner between i and j also fits, because all of them are at
most a[j]. That is j - i pairs confirmed by one comparison, exactly the block count from
problem 608.
## The off-by-one in the subtraction
The second call uses lower - 1, not lower, because the band INCLUDES its lower bound.
Subtracting the count at lower would also remove every pair summing to exactly lower.
1 1 with bounds 2 and 2 answers 1, and 1 1 with bounds 3 and 3 answers 0. Those two inputs
differ only in the bounds, and together they catch this immediately.
## Why the helper needs no special cases
A ceiling below everything lets j fall all the way to i without counting anything. A
ceiling above everything counts every pair. Neither needs its own branch, which is part of why
splitting the band into two calls is simpler than handling it in one sweep.
## Overflow
The count reaches C(200000, 2), about 2 * 10^10, so the COUNT needs 64 bits. Sums reach
2 * 10^9 in magnitude, and lower - 1 goes one below the smallest bound, so keep the
arithmetic in 64 bits throughout.
## Cost
Time O(n log n) for the sort plus two linear sweeps. Space O(1) beyond the input.
Constraints - `0 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - `-10^9 ≤ lower ≤ upper ≤ 10^9`
Input
The first line contains three integers n, lower and upper.
The second line contains n integers. It is absent when n is 0.
Output
Print one integer, the number of position pairs whose sum lies between the bounds.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.