这道题其实有两个版本（usaco两个组）
较难版本的数据量应该是N<=1e5的
这意味着这道题一定有NlogN或时间复杂度接近的解法。
不难想到（模考的时候没想到），我们可以暴力枚举第一刀的情况然后二分第二刀的情况。因为如果只切一刀的时候，二分答案的正确性显然。那么我们切两刀的时候，枚举第一刀，然后第二刀就可以二分答案了。这就相当于一条扫描线。每向前推进一格，将这一条的所有点放入已扫描区域，从未扫描区域删除这些点。显然，我们可以用能维护区间的数据结构来实现。这里我选择了树状数组，读者也可以尝试用线段树。
第一次做的时候，认为要开一个二维树状数组，然后发现，只需要维护一维的就够了，因为我们二分的时候是在一维上二分的。这里可以离散化一下但是洛谷的数据太水了我懒得离散化（雾
代码如下：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define N 100001 int m; int tree[2][N*10]; struct node { int x,y; }e[N]; inline void read(int &x) { x=0;int f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x*=f; } bool cmp(node p,node q) { return p.x<q.x; } inline int lowbit(int i) { return i&(-i); } void add(int t,int x,int w) { while(x<=m) { tree[t][x]+=w; x+=lowbit(x); } } int query(int t,int x) { int sum=0; while(x) { sum+=tree[t][x]; x-=lowbit(x); } return sum; } int main() { int n; read(n); for(int i=1;i<=n;++i) { read(e[i].x); read(e[i].y); m=max(m,e[i].y); } for(int i=1;i<=n;++i) add(1,e[i].y,1); sort(e+1,e+n+1,cmp); int j; int ans=n; int l,r,mid,tmp; int sum0,sum1,tot0,tot1; for(int i=1;i<=n;i=j) { j=i; while(j<=n && e[j].x==e[i].x) { add(1,e[j].y,-1); add(0,e[j].y,1); j++; } l=1; r=m; tot0=query(0,m); tot1=query(1,m); tmp=1; while(l<=r) { mid=l+r>>1; sum0=query(0,mid); sum1=query(1,mid); if(max(sum0,sum1)>=max(tot0-sum0,tot1-sum1)) { tmp=mid; r=mid-1; } else l=mid+1; } sum0=query(0,tmp); sum1=query(1,tmp); ans=min(ans,max(max(sum0,sum1),max(tot0-sum0,tot1-sum1))); } cout<<ans; }