题目大意：平面上有一些红点和黑点，求一个矩形包含最多的红点，不包含黑点，在此基础上要求面积最小
首先不考虑面积最小这个条件 由于x,y<=1000 因此可以利用单调队列/悬线法搞出所有的极大子矩形 对每个子矩形可以O(1)计算出里面有多少红点更新答案
现在要求面积最小 那么我们就对于每个极大子矩形二分消去四周没有点的部分即可
时间复杂度O(n^2logn)
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1010using namespace std;int n,a[M][M],b[M][M];int ans,ans_area;int Get_Points(int x1,int y1,int x2,int y2){return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];}int Bisection1(int x1,int y1,int x2,int y2){int l=0,r=x2-x1;while(l+1<r){int mid=l+r>>1;if( !Get_Points(x1,y1,x1+mid-1,y2) )l=mid;elser=mid;}return !Get_Points(x1,y1,x1+r-1,y2)?r:l;}int Bisection2(int x1,int y1,int x2,int y2){int l=0,r=y2-y1;while(l+1<r){int mid=l+r>>1;if( !Get_Points(x1,y1,x2,y1+mid-1) )l=mid;elser=mid;}return !Get_Points(x1,y1,x2,y1+r-1)?r:l;}int Bisection3(int x1,int y1,int x2,int y2){int l=0,r=y2-y1;while(l+1<r){int mid=l+r>>1;if( !Get_Points(x1,y2-mid+1,×2,y2) )l=mid;elser=mid;}return !Get_Points(x1,y2-r+1,×2,y2)?r:l;}void Calculate(int x1,int y1,int x2,int y2){int temp=Get_Points(x1,y1,x2,y2);if(temp<ans) return ;if(temp>ans)ans=temp,ans_area=0x3f3f3f3f;x1+=Bisection1(x1,y1,x2,y2);y1+=Bisection2(x1,y1,x2,y2);y2-=Bisection3(x1,y1,x2,y2);ans_area=min(ans_area,(x2-x1)*(y2-y1) );}void Monotonous_Stack(int base,int h[]){static int stack[M],l[M],r[M];int i,top=0;for(i=1;i<=1002;i++){while(h[stack[top]]>h[i])r[stack[top–]]=i;stack[++top]=i;}top=0;for(i=1001;~i;i–){while(h[stack[top]]>h[i])l[stack[top–]]=i;stack[++top]=i;}for(i=1;i<=1001;i++)if(h[i])Calculate(base-h[i]+1,l[i]+1,base,r[i]-1);}int main(){int i,j,x,y;char p[10];cin>>n;for(i=1;i<=n;i++){scanf("%d%d%s",&x,&y,p);x++;y++;if(p[0]=='H')a[x][y]++;elseb[x][y]=1;}for(i=1;i<=1001;i++)for(j=1;j<=1001;j++)a[i][j]+=a[i-1][j];for(i=1;i<=1001;i++)for(j=1;j<=1001;j++)a[i][j]+=a[i][j-1];static int h[M];for(i=1;i<=1001;i++){for(j=1;j<=1001;j++)h[j]=b[i][j]?0:h[j]+1;Monotonous_Stack(i,h);}cout<<ans<<endl<<ans_area<<endl;}
，所以你不懂我的选择，也可以不懂我的难过，
