题目链接：[USACO16FEB]负载平衡Load Balancing_Silver

题目大意：给你一个矩阵，里面有些点，让你横向切一刀，纵向切一刀，使得得到的四个区域内的最大的点数最少。

这道题目数据比较水，点的数量是1e3，于是我们可以用前缀和暴力枚举。

但是太没技术含量了，于是我们采用了一种 nlogn * logn 的做法。

我们把点离散化之后，枚举x坐标，然后用两个线段树或者树状数组维护x左右点的y坐标信息。然后二分y坐标即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=2e3+10;
int n,d[2][N],a[N],b[N],m,res=0x3f3f3f3f,tot0,tot1;
vector<int> x[N],v;
inline int id(int x){
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
inline void add(int k,int x,int v){
	for(;x<=m;x+=lowbit(x))	d[k][x]+=v;
}
inline int ask(int k,int x){
	int res=0; for(;x;x-=lowbit(x)) res+=d[k][x]; return res;
}
inline int check(int mid){
	int cnt0=ask(0,mid); int cnt1=ask(1,mid);
	return (max(cnt0,cnt1)>=max(tot0-cnt0,tot1-cnt1));
}
inline int bsearch(){
	int l=0,r=m; tot0=ask(0,m); tot1=ask(1,m);
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))	r=mid;
		else	l=mid+1;
	}
	int cnt0=ask(0,l);	int cnt1=ask(1,l);
	return max(max(cnt0,cnt1),max(tot0-cnt0,tot1-cnt1));
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];	v.push_back(a[i]); v.push_back(b[i]);
	}
	sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
	m=v.size();
	for(int i=1;i<=n;i++)	x[id(a[i])].push_back(id(b[i]));
	for(int i=1;i<=n;i++)	add(1,id(b[i]),1);
	for(int i=0;i<=m;i++){
		for(int j=0;j<x[i].size();j++)	add(0,x[i][j],1),add(1,x[i][j],-1);
		res=min(res,bsearch());
	}
	cout<<res<<endl;
	return 0;
}