B. Fortress

首先，观察式子 $r_1\le x_i\le r_2,c_1\le y_i\le c_{2}r\_1\; \backslash le\; x\_i\; \backslash le\; r\_2,c\_1\; \le \; y\_i\; \le \; c\_2$ 可以发现，我们需要找到是一个十字架覆盖所有的点（而不是矩形），所求矩形是十字架的横竖边相交的矩形。那么，一行 $mm$ 列和 $nn$ 行一列的矩形构成的十字架必定可以覆盖，所以最小值最大只会是 $min(n,m)min(n,m)$ 。

接下来，我们可以很容易的想到一个 $n^{5}n^5$ 的做法，那就是枚举矩形的四条边，然后对每个点检查，但显然这样过不去。

不那么容易的可以想到一个优化方法是，只枚举左右两边 $c_1,c_{2}c\_1,c\_2$ （宽度），那么删去这两边之中的点后（此部分怪物可以由十字架竖边解决），只需找到剩余点（两边之外的点）的最高最低值，两者相差即是高度，此时我们成功的将 $n^{5}n^5$ 优化到了 $n^{3}n^3$ 。

找到两边之外的点的最高最低值，也就是要找到 $[1,c_1),(c_2,m][1,c\_1),(c\_2,m]$ 区间中的最大最小值，区间求最值我们不难想到可以用 线段树 ST表 （我当时就写的是ST表，现在想想我是傻*），可以在排序后用四个数组 $O(n)O(n)$ 预处理从前往后、从后往前的最值，此时我们已经将做法优化到了 $n^{2}n^2$ （虽然还是过不去）。

非常不要脸的可以问到（指赛后问大佬），由于答案最大为 $min(n,m)min(n,m)$ （接下来假设 $nn$ 小于 $mm$） ，那么，我们枚举宽度时:

• 若 $c_2-c_1+1>\sqrt{n}c\_2-c\_1+1\; >\; \backslash sqrt\{n\}$ ，则没有枚举的必要——如果这个宽度是答案， 必须成立，此时的 $r_1,r_{2}r\_1,r\_2$ 将会在枚举高度时枚举到；否则答案大于 $nn$ ，没有意义。

• 若 $c_2-c_1+1\le \sqrt{n}c\_2-c\_1+1\; \backslash le\; \backslash sqrt\{n\}$ ，则用上述方法 $O(1)O(1)$ 的算出 $r_1,r_{2}r\_1,r\_2$ 将答案与 $(r_2-r_1+1)\ast (c_2-c_1+1)(r\_2-r\_1+1)*(c\_2-c\_1+1)$ 取最小值。

枚举高度时同理。

此时，时间复杂度成功的变成了 $max(n,m)\ast \sqrt{min(n,m)}max(n,m)*\backslash sqrt\{min(n,m)\}$ ，终于到了可以通过的程度。

鸣谢一位不知道愿不愿意透露姓名的神佬！

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back

using namespace std;

using LL = long long;
using LD = long double;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

const int N = 1e6+5;
const LL M = 1e9+7;
const LD pi=acos(-1);

LL n,m,k,T;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m>>k;
	vector<PII> a(k+1);
	auto init = [&](LL u)->LL{
		vector st(k+2,vector<PII>(21,{1e9,0}));
		vector<int> lo(k+1),l(n+m+1),r(n+m+1);
		lo[0]=lo[1]=0;
		for(int i=1;i<=20;i++){
			for(int j=1<<i;j<min((int)(k+1),1<<i+1);j++) lo[j]=i;
		}
		for(int i=1;i<=k;i++) st[i][0].x=st[i][0].y=a[i].y;
		for(int i=1;i<=k;i++) r[a[i].x]=i;
		for(int i=k;i>0;i--) l[a[i].x]=i;
		for(int j=1;j<=20;j++){
			int t=1<<j;
			for(int i=1;i+t-1<=k;i++){
				st[i][j].x=min(st[i][j-1].x , st[i+t/2][j-1].x);
				st[i][j].y=max(st[i][j-1].y , st[i+t/2][j-1].y);
			}
		}
		int ans=1e9;
		for(int i=1;i<=u;i++){
			if(!l[i]) continue;
			for(int j=i;(j-i+1)*(j-i+1)<=u && j<=u;j++){
				if(!r[j]) continue;
				int L=l[i]-1,R=r[j]+1;
				int t1=lo[L] , t2=lo[k-R+1];
				int mi=1e9;
				if(L>0) mi = min(st[1][t1].x , st[L-(1<<t1)+1][t1].x);
				if(R<=k) mi = min({mi , st[R][t2].x , st[k-(1<<t2)+1][t2].x});
				int ma=0;
				if(L>0) ma = max(st[1][t1].y , st[L-(1<<t1)+1][t1].y);
				if(R<=k) ma = max({ma , st[R][t2].y , st[k-(1<<t2)+1][t2].y});
				ans = min(ans,(j-i+1)*(ma-mi+1));
			}
		}
		return ans;
	};
	for(int i=1;i<=k;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a.begin()+1,a.end());
	LL ans = init(n);
	for(auto &[x,y] : a) swap(x,y);
	sort(a.begin()+1,a.end());
	ans = min(ans , init(m));
	cout<<ans<<endl;
	return 0;
}
/*
此代码仅供参考，脑子抽了才会去写ST表
*/