Descripción del Problema

Se te proporciona una secuencia de (n) enteros, donde el (i)-ésimo elemento es (a_i). Además, se dan dos enteros (x) y (y) (con (x \le y)).

Un par de enteros ((i, j)) se considera interesante si cumple las siguientes condiciones:

• (1 \le i < j \le n);
• Si se eliminan los elementos en las posiciones (i) y (j) de la secuencia, la suma de los elementos restantes está entre (x) y (y) inclusive.

Tu tarea es determinar el número de pares interesantes en la secuencia dada.

Entrada

La primera línea contiene un entero (t) ((1 \le t \le 10^4)) - el número de casos de prueba.

Cada caso de prueba consiste en dos líneas:

• La primera línea contiene tres enteros (n, x, y) ((3 \le n \le 2 \cdot 10^5), (1 \le x \le y \le 2 \cdot 10^{14}));
• La segunda línea contiene (n) enteros (a_1, a_2, \dots, a_n) ((1 \le a_i \le 10^9)).

Restricción adicional: la suma de todos los (n) en todos los casos de prueba no excede (2 \cdot 10^5).

Salida

Para cada caso de prueba, imprime un entero - el número de pares interesantes en la secuancia dada.

Ejemplo

Entrada

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
  

Salida

4
7
0
0
1
5
6
  

Enfoque para la Solución

Primero, derivamos la fórmula. Dado que la secuencia es un arreglo (A) y (S = \sum_{i=1}^n A[i]), la condición para un par ((i, j)) ser enteresante es:

(x \le S - A[i] - A[j] \le y)

Esto implica:

(S - y - A[i] \le A[j] \le S - x - A[i])

Podemos enuemrar (A[i]) para obtener el rango de (A[j]) y contar cuántos elementos caen en ese rango. Para manejar los grandes rangos, usamos discretización y búsqueda binaria.

Es importante notar que este método también cuenta pares donde (i = j) o (i > j), por lo que debemos ajustar el resultado final restando estos casos.

Código

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 2e5 + 5;

void solve() {
    ll n, x, y;
    cin >> n >> x >> y;

    ll S = 0;
    vector<ll> A(n), B(3 * n + 1);
    vector<ll> dct;
    dct.push_back(-1E18); // Sentinela para evitar desbordamiento

    for (int i = 0; i < n; i++) {
        cin >> A[i];
        S += A[i];
    }

    for (int i = 0; i < n; i++) {
        dct.push_back(A[i]);
        dct.push_back(S - x - A[i]);
        dct.push_back(S - y - A[i]);
    }

    sort(dct.begin(), dct.end());
    dct.erase(unique(dct.begin(), dct.end()), dct.end());

    auto find = [&](ll p) -> int {
        return lower_bound(dct.begin(), dct.end(), p) - dct.begin();
    };

    for (int i = 0; i < n; i++) {
        B[find(A[i])] += 1;
    }
    for (int i = 1; i < 3 * n + 1; i++) {
        B[i] += B[i - 1];
    }

    ll res = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        res += B[find(S - x - A[i])] - B[find(S - y - A[i]) - 1];
        if (S - A[i] - A[i] >= x && S - A[i] - A[i] <= y) ans++;
    }

    cout << (res - ans) / 2 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(2);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}