蒟蒻实在太菜，只能提供一种 非正解 的简单做法，通俗易懂，不用晦涩难懂的数学公式
巨佬的线段树维护凸包我不会，那就只好上随机化了
一看这道题目要求最值，那就是非常明显的st表了
相信大家都会吧
不会的先干了P3865
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-n 的升序排列时，时间复杂度接近 n^2 ，快乐拿下 TLE 20
于是随机化就有了
用系统函数 random_shuffle(p.begin(),p.end())就可以让p数组重新随机排列，这样就不用担心 TLE 了 基本卡不掉，充分发扬人类智慧
代码如下：
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-j 区间后，会有一些区间一定不比当前优,因为它们再大也不会比 ans 大
以下记 qx = queryx(i , j) , qy = queryy(i , j) , q = qx \times qy
现在我们枚举到了 (i , j) ,期望找到下一个枚举到的 j' > j 使 ans' = (j' - i + 1) \times q' > 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;//最优化数学剪枝
}
}
完结撒花！！！
最后说一句：random_shuffle() ，只支持C++17前的，后被弃用，变成了shuffle()函数
