#include <vector>
#include <algorithm>
using namespace std;
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
long long total_empty = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j] == 0) total_empty++;
}
}
// 特判：全满（都是树）或全空
if (total_empty == N * N) return N * N;
if (total_empty == 0) return 0;
// 预处理每一行：各空地向左和向右延伸的连续空地数量（包含自身）
vector<vector<int>> L_row(N, vector<int>(N, 0));
vector<vector<int>> R_row(N, vector<int>(N, 0));
for (int r = 0; r < N; ++r) {
int cnt = 0;
for (int c = 0; c < N; ++c) {
if (F[r][c] == 0) cnt++;
else cnt = 0;
L_row[r][c] = cnt;
}
cnt = 0;
for (int c = N - 1; c >= 0; --c) {
if (F[r][c] == 0) cnt++;
else cnt = 0;
R_row[r][c] = cnt;
}
}
// 辅助函数：利用单调栈 O(len) 求出每个位置为基准向左侧延展构成的最大合规前缀面积
auto compute_pref = [&](const vector<int>& A, vector<int>& pref, vector<int>& st) {
int n = A.size();
st.clear();
for (int i = 0; i < n; ++i) {
while (!st.empty() && A[st.back()] >= A[i]) {
st.pop_back();
}
int prev_idx = st.empty() ? -1 : st.back();
int prev_val = st.empty() ? 0 : pref[prev_idx];
pref[i] = prev_val + (i - prev_idx) * A[i];
st.push_back(i);
}
};
// 辅助函数：利用单调栈 O(len) 求出每个位置为基准向右侧延展构成的最大合规后缀面积
auto compute_suff = [&](const vector<int>& A, vector<int>& suff, vector<int>& st) {
int n = A.size();
st.clear();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && A[st.back()] >= A[i]) {
st.pop_back();
}
int next_idx = st.empty() ? n : st.back();
int next_val = st.empty() ? 0 : suff[next_idx];
suff[i] = next_val + (next_idx - i) * A[i];
st.push_back(i);
}
};
int max_area = 0;
// 提前预分配内存以避免运行中动态分配耗时
vector<int> L, R, pref_L, suff_L, pref_R, suff_R, st;
L.reserve(N); R.reserve(N);
pref_L.reserve(N); suff_L.reserve(N);
pref_R.reserve(N); suff_R.reserve(N);
st.reserve(N);
// 遍历每一个列作为球场的 "核心中轴列 c"
for (int c = 0; c < N; ++c) {
int u = 0;
while (u < N) {
if (F[u][c] == 1) { // 遇到树则重置段落
u++;
continue;
}
int d = u;
// 找出包含 c 的一段在列向上的连续空单元格骨架 [u, d]
while (d + 1 < N && F[d + 1][c] == 0) {
d++;
}
int len = d - u + 1;
L.resize(len); R.resize(len);
pref_L.resize(len); suff_L.resize(len);
pref_R.resize(len); suff_R.resize(len);
for (int k = u; k <= d; ++k) {
L[k - u] = L_row[k][c];
R[k - u] = R_row[k][c];
}
compute_pref(L, pref_L, st);
compute_suff(L, suff_L, st);
compute_pref(R, pref_R, st);
compute_suff(R, suff_R, st);
// 组合左右独立求出的最大单侧面积以汇聚成最大截面
for (int m = 0; m < len; ++m) {
// 左翼最大贡献 + 右翼最大贡献 - 叠加扣减（本身长度在左右计算时被多加了一次，同时每行中心列基础占位扣除）
int area = pref_L[m] + suff_L[m] - L[m]
+ pref_R[m] + suff_R[m] - R[m]
- len;
if (area > max_area) {
max_area = area;
}
}
u = d + 1;
}
}
return max_area;
}
