题目描述
城市游戏再扩展
https://www.acwing.com/file_system/file/content/whole/index/content/2312847/
求更改(x,y)上下左右四个长方形的面积(4遍城市游戏)中的最大值
使用stack时间超了,换了数组模拟栈
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
const int N = 2010;
int n,m,h[N][N],l[N],r[N];
int U[N],D[N],L[N],R[N];
char map[N][N];
int s[N];
int cal(int h[],int k){
h[0] = h[k+1] = -1;
int tt = 0;
s[tt] = 0;
for (int i = 1; i <= k; i ++ ){
while(h[i] <= h[s[tt]])tt--;
l[i] = s[tt];
s[++tt] = i;
}
tt = 0;
s[tt] = k+1;
for (int i = k; i > 0 ; i -- ){
while(h[i] <= h[s[tt]])tt--;
r[i] = s[tt];
s[++tt] = i;
}
/* stack<int> sl;
sl.push(0);
for (int i = 1; i <= k; i ++ ){
while(h[i] <= h[sl.top()])sl.pop();
l[i] = sl.top();
sl.push(i);
}
stack<int> sr;
sr.push(k+1);
for (int i = k; i > 0; i -- ){
while(h[i] <= h[sr.top()])sr.pop();
r[i] = sr.top();
sr.push(i);
}*/
int res = 0;
for (int i = 1; i <= k; i ++ )
res = max(res,h[i] * (r[i] - l[i] - 1));
return res;
}
void init(){
//上
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
if(map[i][j] == '1')h[i][j] = h[i-1][j] + 1;
else h[i][j] = 0;
}
U[i] = max(U[i-1],cal(h[i],m));
}
//下
memset(h,0,sizeof h);
for(int i = n;i > 0;i--){
for(int j = 1;j <= m;j++){
if(map[i][j] == '1')h[i][j] = h[i+1][j] + 1;
else h[i][j] = 0;
}
D[i] = max(D[i+1],cal(h[i],m));
}
//左
memset(h,0,sizeof h);
for (int i = 1; i <= m; i ++ ){
for (int j = 1; j <= n; j ++ ){
if(map[j][i] == '1')h[i][j] = h[i-1][j] + 1;
else h[i][j] = 0;
}
L[i] = max(L[i-1],cal(h[i],n));
}
//右
memset(h,0,sizeof h);
for (int i = m; i > 0; i -- ){
for (int j = 1; j <= n; j ++ )
{
if(map[j][i] == '1')h[i][j] = h[i+1][j] +1;
else h[i][j] = 0;
}
R[i] = max(R[i+1],cal(h[i],n));
}
}
int main()
{
scanf("%d %d",&n,&m);
for (int i = 1; i <= n; i ++ )scanf("%s",map[i] + 1);
init();
int Q;
scanf("%d", &Q);
while(Q--){
int x,y;
scanf("%d %d",&x,&y);
x++ ;y++;
int res = max(max(U[x-1],D[x+1]),max(L[y-1],R[y+1]));
printf("%d\n",res);
}
return 0;
}