提供一种 $O(n\log n)$ 的做法。

实际上本题可以不需要二分。考虑枚举竖直栅栏 $x=a$ 的 $a$。用树状数组维护它左右的点。在树状数组上倍增找到最大的满足以下条件的 $b$。

条件：画出直线 $x=a$ 和 $y=b$，将平面分为左下、右下、左上、右上四个部分。设四个部分中的点数分别为 $c_1,c_2,c_3,c_4$，则 $\max(c_1,c_2)\le\max(c_3,c_4)$。说人话就是下面两块的点数的较大值不超过上面两块的点数较大值。

那么，假如竖直栅栏被钦定为直线 $x=a$，那么最优（使得 $M$ 最小）的水平栅栏一定是直线 $y=b$ 或者直线 $y=b+2$。

证明：设水平栅栏下方两块的点数较大值为 $max_1$，上方两块的点数较大值为 $max_2$。显然水平栅栏为直线 $y=b$ 的时候 $max_1\le max_2$，水平栅栏为直线 $y=b+2$ 的时候 $max_1>max_2$。设 $b'<b$，则此时显然 $max_2'$ 不小于原来的 $max_2$，答案不减。$b'>b+2$ 时同理。

时间复杂度 $O(max_x+n\log{max_y})$。可以离散化做到 $O(n\log n)$。

由于我懒，所以代码实现没有离散化。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m,t1[1000005],t2[1000005],x,n1,n2;
const int N=1e6;
vector<int>g[1000005];
void add1(int x,int y){n1+=y;while(x<=N)t1[x]+=y,x+=x&-x;}
void add2(int x,int y){n2+=y;while(x<=N)t2[x]+=y,x+=x&-x;}
int calc()
{
	int res=0,l1=0,l2=0,ret=0x3f3f3f3f;
	for(int i=1<<19;i;i>>=1)//树状数组上倍增，一个很好玩的trick
    //可以用线段树上二分代替
	{
		int c1=l1+t1[res+i],c2=l2+t2[res+i];
		if(max(c1,c2)<=max(n1-c1,n2-c2))res+=i,l1=c1,l2=c2;
		else ret=min(ret,max(c1,c2));
        //不想写query函数查询y<=res+2的点个数，所以直接取了很多次多余的min
	}
	ret=min(ret,max(n1-l1,n2-l2));
	return ret;
}
int main()
{
	scanf("%d",&n);
	int mx=0;
	for(int i=1,x,y;i<=n;++i)
		scanf("%d%d",&x,&y),g[x].push_back(y),
		mx=max(mx,x+1),add2(y,1);
	int ans=0x3f3f3f3f;
	for(int i=2;i<=mx;i+=2)if(g[i-1].size())
	{
		for(auto x:g[i-1])add1(x,1),add2(x,-1);
		ans=min(ans,calc());
	}
	printf("%d\n",ans);
}

我看到这个题目是真的没思路，然后看题解还只有一个而且没几行讲思路，快哭了$QAQ$。

为了避免别人也有我这种糟糕的体验，这篇题解诞生了。

先看题目，最大值最小，学过OI的都知道这要用到二分，直接二分枚举答案再$check$就好了。

再看$check$要怎么写。

设我们枚举的答案是$ans$，则我们分出来的每个区域的奶牛都要小于$ans$显而易见。

我们枚举 $y$ ，用两个树状数组维护 $y$ 上面区域和下面的奶牛数，然后求一个最优的 $x$。

但是如果直接枚举$x$，时间复杂度会直接到$n^2$，很明显不能直接枚举。

再仔细想想，假设我们是从小到大枚举$y$，那么上面区域的奶牛数会越来越少，下面的奶牛的数量会越来越多，所以对于上面区域，我们从小到大枚举$x$，设左上区域奶牛数刚好$<=ans$时$x=t1$，对于下面区域，我们从大到小枚举$x$，设左下区域奶牛数刚好$<=ans$时$x=t2$，则最优的$x$就是$min(t1,t2)$

$x$和$y$都确定了，再计算出其他两个区域的奶牛数就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;

inline int read()
{
	int res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res;
}

struct Cow{
	int x,y;
	bool operator <(const Cow a) const{
        return y<a.y;
    }
}c[N];

int n,sb[N],xb[N];
#define lowbit(x) (x)&(-x)
void change(int a[],int x,int k)
{
	while(x<=n)
		a[x]+=k,x+=lowbit(x);
}

int query(int a[],int x)
{
	int res=0;
	while(x>0)
		res+=a[x],x-=lowbit(x);
	return res;
}

bool check(int x)
{
	memset(sb,0,sizeof(sb));
	memset(xb,0,sizeof(xb));
	for(int i=1;i<=n;i++)
		change(sb,c[i].x,1);
	int st=n,xt=0,zs=1,zx=n;
	for(int t,i=1,j=1;i<=n;i=j)
	{
		while(c[i].y==c[j].y)
			change(sb,c[j].x,-1),change(xb,c[j].x,1),st--,xt++,j++;
		while(zs<=n&&query(sb,zs)<=x)
			zs++;
		zs--;
		while(zx>0&&query(xb,zx)>x)
			zx--;
		t=min(zx,zs);
		if(xt-query(xb,t)<=x&&st-query(sb,t)<=x)
			return true;
	}
	return false;
}

pair<int,int>p[N];

int tot,mid,l,r,ans;

int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		c[i].x=read(),c[i].y=read(),p[i].first=c[i].x,p[i].second=i;
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++)
	{
		if(p[i].first!=p[i-1].first)
			tot++;
		c[p[i].second].x=tot;
	}
	sort(c+1,c+n+1);
	l=1,r=n;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))
			r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d\n",ans);
    return 0;
}