这题。。 我真傻，真的。。我单知道单调队列可以优化dp，加上平衡树，却不知道单调栈就可以。。
求给定矩形最大的同字母矩形面积。(字母数：a,b,c) 多组数据$n,m≤1000$
真的学傻掉了。。写出来一个$O(n^3)$dp方程还跟真的一样去想优化。。最后只能做到$O(n^2logn)$。。
一开始大体就是对于每行的每个字母，都可以统计出前i行这一列到他最长维持多少个相同字母。这就是像是个直方图，然后去找最大面积即可。
$S = max{min(a[i]～a[j])*(j-i+1)}$
这个并不需要dp。观察一下，这不就是上天那个和良好的感觉差不多的题吗？枚举每个点，拓展两边直到找到比他小（矮）的，算下面积。
列一下犯的错误：
- 单调栈重更新底部初始元素
- 从上一行转移过来的最长相同字母子串当无法转移（不相同时）要断开，重置为零。（这个普及组都不该犯的错啊啊啊啊啊啊！）
我还是太菜了啊。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 typedef long long ll; 9 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 10 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 11 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 12 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 13 template<typename T>inline T read(T&x){ 14 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 15 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 16 } 17 const int N=1000+7; 18 char s[N]; 19 int h[N][3],q[N],f[N]; 20 int n,m,l,r,ans; 21 22 inline void get_h(int j){ 23 switch(s[j]){ 24 case 'a':++h[j][0],h[j][1]=h[j][2]=0;break; 25 case 'b':++h[j][1],h[j][0]=h[j][2]=0;break; 26 case 'c':++h[j][2],h[j][0]=h[j][1]=0;break; 27 case 'w':++h[j][0],++h[j][1],h[j][2]=0;break; 28 case 'x':++h[j][1],++h[j][2],h[j][0]=0;break; 29 case 'y':++h[j][0],++h[j][2],h[j][1]=0;break; 30 case 'z':++h[j][0],++h[j][1],++h[j][2];break; 31 } 32 } 33 inline void dp(int p){ 34 l=1,q[r=0]=0;//注意更新q[0]！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ 35 for(register int i=1;i<=m;++i){ 36 while(l<=r&&h[q[r]][p]>=h[i][p])--r; 37 f[i]=q[r]+1,q[++r]=i; 38 } 39 l=1,q[r=0]=m+1;//注意更新 40 for(register int i=m;i;--i){ 41 while(l<=r&&h[q[r]][p]>=h[i][p])--r; 42 MAX(ans,(q[r]-f[i])*h[i][p]),q[++r]=i; 43 } 44 } 45 46 int main(){//freopen("test.in","r",stdin);//freopen("tmp.out","w",stdout); 47 while(~scanf("%d%d",&n,&m)){ 48 ans=0;memset(h,0,sizeof h); 49 for(register int i=1;i<=n;++i){ 50 scanf("%s",s+1); 51 for(register int j=1;j<=m;++j)get_h(j); 52 dp(0),dp(1),dp(2); 53 } 54 printf("%d ",ans); 55 } 56 return 0; 57 }