题解 | 四值零和

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N = 2510;

//查找a中有多少target 
int calcu(long long a[], int n, long long target) {
	if (a[0] > target || a[n - 1] < target) return 0;
	//查找下界
	int l = 0, r = n - 1;
	while (r > l) {
		int mid = (r - l) / 2 + l;
		if (a[mid] >= target) r = mid;
		else l = mid + 1;
	}
	int down = l;
	if (a[down] != target) return 0; 
	if (a[n - 1] == target) {
		return n - down;
	} else {
		l = 0, r = n - 1;
		while (r > l) {
			int mid = (r - l) / 2 + l;
			if (a[mid] <= target) l = mid + 1;
			else r = mid;
		}
		return l - down;
	} 
} 

int main() {
	int n;
	cin >> n;
//	vector<vector<ll> > a(n, vector<ll>(4));
	ll** a = new ll*[n + 1];
	for (int i = 0; i < n; i++) {
		a[i] = new ll[4];
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
	}
	ll** processed = new ll*[2];
	processed[0] = new ll[N * N];
	processed[1] = new ll[N * N];
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
//			processed[cnt] = new ll[2];
			processed[0][cnt] = a[i][0] + a[j][1];
			processed[1][cnt++] = (a[i][2] + a[j][3]) * -1;
		}
	}
	sort(processed[1], processed[1] + cnt);
	long long ans = 0;
	for (int i = 0; i < cnt; i++) {
		//二分查找上下界 
		ans += calcu(processed[1], cnt, processed[0][i]);
	}
	cout << ans << endl;
}