题解：P7164 [COCI2020-2021#1] 3D Histogram

# 前置芝士： ST表，随机化

蒟蒻实在太菜，只能提供一种 ~~非正解~~ 的简单做法，通俗易懂，不用晦涩难懂的数学公式。

没看过题目的点[这里](https://www.luogu.com.cn/problem/P7164)。

巨佬的线段树维护凸包我不会，那就只好上骚操作了。

一看这道题目要求最值，我就感觉是st表了。

st表是很好维护的:
```
void init(){
	for(int i=1;i<=n;++i) stx[i][0]=a[i].x,sty[i][0]=a[i].y;
	for(int j=1,t=1;j<=23;++j,t*=2){
		for(int i=1;i<=n-2*t+1;++i){
			stx[i][j]=min(stx[i][j-1],stx[i+t][j-1]);
			sty[i][j]=min(sty[i][j-1],sty[i+t][j-1]);
		}
	}
}
```

也是非常容易查询的：
```
int queryx(int l,int r){
	int lg=log2(r-l+1);
	return min(stx[l][lg],stx[r-(1<<lg)+1][lg]);
}
int queryy(int l,int r){
	int lg=log2(r-l+1);
	return min(sty[l][lg],sty[r-(1<<lg)+1][lg]);
}
```

但是当有一组数据为 $1 \sim n$ 的升序排列时，时间复杂度接近 $n^2$ ，快乐拿下 TLE 20。

于是就有了随机化的思路。

用系统函数 `random_shuffle(p.begin(),p.end())`就可以让p数组重新随机排列，这样就不用担心ST表复杂度暴增了。

代码如下：
```
for(int i=1;i<=n;++i) p.push_back(i);
random_shuffle(p.begin(),p.end());//随机化，防止被卡 
```
但是如果这样，提交上去还是会拿到光荣的 TLE 20。

蒟蒻思考良久，终于在统计答案的时候发现了一个有点玄学的优化。

原来的统计是这样的：
```
for(int i : p){
  for(int j=i;j<=n;++j){
    int cnt=queryx(i,j)*queryy(i,j);
    ans=max(ans,(j-i+1)*cnt);
  }
}
```

我们发现，在统计完现在的 $i \sim j$ 区间后，会有一些区间一定不比当前优，因为它们再大也不会比 $ans$ 大。

以下记 $qx = queryx(i , j)$ , $qy = queryy(i , j)$ , $q = qx \times qy$

现在我们枚举到了 $(i , j)$ ,期望找到下一个枚举到的 $j' > j$ 使 $ans' = (j' - i + 1) \times q' \ge ans$

以下记 $j - i + 1 = len$ , $j' - i + 1 = len'$

非常显然，由于我们预处理st表是求 $\min$ ,那么容易发现， $q \ge q'$

那就意味我们可以构造一个不等式:

$len' \times q' \ge ans$

$\therefore len' \times q \ge ans$

$\therefore len' \ge \frac{ans}{q}$

$\therefore j' \ge \frac{ans}{q} + i - 1$

于是我们的最优化数学剪枝就做完了。

代码如下：
```
for(int i : p){
  for(int j=i;j<=n;++j){
    int cnt=queryx(i,j)*queryy(i,j);
    ans=max(ans,(j-i+1)*cnt);
    j=(ans/cnt)+i-1;//最优化数学剪枝
  }
}
```

完整代码如下：
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,stx[200005][23],sty[200005][23],ans;
struct node{
	int x,y;
}a[200005];
inline int read(){
	register int x=0,f=1;
	char c;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void init(){
	for(int i=1;i<=n;++i) stx[i][0]=a[i].x,sty[i][0]=a[i].y;
	for(int j=1,t=1;j<=23;++j,t*=2){
		for(int i=1;i<=n-2*t+1;++i){
			stx[i][j]=min(stx[i][j-1],stx[i+t][j-1]);
			sty[i][j]=min(sty[i][j-1],sty[i+t][j-1]);
		}
	}
}
int queryx(int l,int r){
	int lg=log2(r-l+1);
	return min(stx[l][lg],stx[r-(1<<lg)+1][lg]);
}
int queryy(int l,int r){
	int lg=log2(r-l+1);
	return min(sty[l][lg],sty[r-(1<<lg)+1][lg]);
}
signed main(){
	n=read();
	for(int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();
	vector<int> p;
	for(int i=1;i<=n;++i) p.push_back(i);
	random_shuffle(p.begin(),p.end());//随机化，防止被卡 
	init();
	for(int i : p){
		for(int j=i;j<=n;++j){
			int cnt=queryx(i,j)*queryy(i,j);
			ans=max(ans,(j-i+1)*cnt);
			j=(ans/cnt)+i-1;//最优化数学剪枝
		}
	}
	cout<<ans;
}
//机房巨佬wyy赛时用随机化切掉了这题 ，orz
```

最后说一句，`random_shuffle()`，只支持C++17前的，后被弃用，变成了`shuffle()`函数。

正在渲染内容...