#include <stdio.h>
int main()
{
puts("转载请注明出处[vmurder]谢谢");
puts("网址：blog.csdn.net/vmurder/article/details/44095063");
}坐标系上给出n个点，分”H”和”G”，1个整点坐标上最多1个点。
现在求1个不包括”G”的包括尽可能多”H”的子矩形，然后在保证”H”最多的情况下还要问最小面积。
输出”H”的最大数量，和保证”H”最多时的最小矩形面积。
我们发现由于坐标有限制[0,1000] (注意有”0”!!!)，所以它是1个矩形。
首先我们可以参照极大子矩形的做法算出所有的极大子矩形，然后保护1个
以后我们可以把每一个极大子矩形过剩的边角砍掉来算面积。
我们可以进行2分，看4个方向都能砍多少，check判的是矩形内”H”的个数是不是为0。
固然，左右其实可以均摊O(1)算出来，诶我现在才发现都已加了logn了，左右消减还写甚么O(1)啊，噗Qwq。
那就不说了，想知道的自己去看代码吧。
还有就是下面不需要削。
不写了不写了，不懂的留言吧。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1010
#define inf 0x3f3f3f3f
using namespace std;
int map[N][N],f[N][N];
struct Data
{
int H,h; // 最高距离、最近白点
int l,r; // 左右有效距离
}s[N];
int ansa,ansb=inf;
int q[N];
inline int getans(int a,int b,int c,int d){return f[d][b]-f[d][a]-f[c][b]+f[c][a];}
inline int getarea(int a,int b,int c,int d)
{
int l=c,r=d,mid,ans;
while(l<=r)
{
if(r-l<=3)
{
ans=l;
for(int i=r;i>=l;i--)
if(getans(a,b,c,i)==0)
{ans=i;break;}
break;
}
mid=l+r>>1;
if(getans(a,b,c,mid)==0)l=mid;
else r=mid-1;
}
return (b-a-1)*(d-ans-1);
}
int main()
{
int i,j,k;
int a,b,c;
scanf("%d",&c);
char ss[5];
while(c--)
{
scanf("%d%d%s",&a,&b,ss),a++,b++;
if(ss[0]=='H')map[a][b]=1; // 可
else map[a][b]=2; // 否
}
for(i=1;i<=1001;i++)
{
int temp=0;
for(j=1;j<=1001;j++)
{
if(map[i][j]==1)temp++;
f[i][j]=f[i-1][j]+temp;
}
}
for(i=1;i<=1001;i++)s[i].h=inf;
int l,r;
for(i=1;i<=1001;i++)
{
for(j=1;j<=1001;j++)
{
if(map[i][j]==2)s[j].H=0,s[j].h=inf;
else {
s[j].H++;
if(map[i][j]==1)s[j].h=1;
else s[j].h++;
}
s[j].l=s[j].r=j;
}
l=1,r=0;
for(j=1;j<=1001;j++)
{
while(l<=r&&s[q[r]].H>=s[j].H)s[j].l=s[q[r--]].l;
while(s[j].l<j&&s[s[j].l].h>s[j].H)s[j].l++;
q[++r]=j;
}
l=1,r=0;
for(j=1001;j;j--)
{
while(l<=r&&s[q[r]].H>=s[j].H)s[j].r=s[q[r--]].r;
while(s[j].r>j&&s[s[j].r].h>s[j].H)s[j].r--;
q[++r]=j;
}
for(j=1;j<=1001;j++)
{
int ret=getans(s[j].l-1,s[j].r,i-s[j].H,i);
if(ret>=ansa)
{
int temp=getarea(s[j].l-1,s[j].r,i-s[j].H,i);
if(ret==ansa)ansb=min(ansb,temp);
else ansa=ret,ansb=temp;
}
}
}
printf("%d
%d
",ansa,ansb);
return 0;
}