四数之和

直接思路为什么不行

四重循环显然炸) 考虑用分组二分做，先预处理两个数的和，然后在求第三和第四个数的和，在前面预处理好的数组中二分他的相反数，用upper_bound-lower_bound得到的区间刚好就是答案，最后累加到一起。

#include <bits/stdc++.h>
using namespace std;
// ========== Fast IO ==========
#define FAST_IO                  \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr)
// ========== 数据类型 ==========
using ll = long long;
using ull = unsigned long long;
using ld = long double;

template <class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using maxpq = priority_queue<T>;

const ll INF64 = (1LL << 62);
const int INF32 = (1 << 30);
const int MOD = 1'000'000'007;
const ld EPS = 1e-12;

// 方向 (4 / 8 邻接)
int dx4[4] = {1, -1, 0, 0};
int dy4[4] = {0, 0, 1, -1};
int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy8[8] = {1, 0, -1, 1, -1, 1, 0, -1};



// ========== 二分 ==========
template <class F>
ll first_true_ll(ll lo, ll hi, F pred)
{ // 找到最小的 x∈[lo,hi] 使 pred(x)=true
    while (lo < hi)
    {
        ll mid = lo + (hi - lo) / 2;
        if (pred(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

template <class F>
ll last_true_ll(ll lo, ll hi, F pred)
{ // 找到最大的 x∈[lo,hi] 使 pred(x)=true
    while (lo < hi)
    {
        ll mid = lo + (hi - lo + 1) / 2;
        if (pred(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;
}
vector<ll> A(5000);
vector<ll> B(5000);
vector<ll> C(5000);
vector<ll> D(5000);
int n;
// ========== Solve ==========
void solve()
{
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    vector<ll> CDS;
    ll ret = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            CDS.push_back(C[i] + D[j]);
        }
    }
    sort(CDS.begin(), CDS.end());
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            ll sum = A[i] + B[j];
            ret += upper_bound(CDS.begin(), CDS.end(), -sum) - lower_bound(CDS.begin(), CDS.end(), -sum);
        }
    }
    cout << ret << "\n";
    return;
}

// ========== Main ==========
int main()
{
    FAST_IO;
    // 重定向：
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

    solve();
    return 0;
}
···