q次询问,每次询问可以对矩阵某一个值改变(0变1,1变0) 或者是查询子矩阵的最大面积,要求这个这个点在所求子矩阵的边界上,且子矩阵各店中全为1
用up[i][j]表示(i,j)这个点向上能走到的最长高度 若(i,j)为0 则up[i][j]值为0
则每次查询时,从up[i][j]枚举至1作为子矩阵的高度,然后途中分别向左右扩展。若up[i][j - 1] >= up[i][j],则可向左扩展一个单位,答案为(r - l - 1) * 高度
同理,四个方向分别枚举
//#pragma comment(linker, "/STACK:102400000,102400000") //HEAD #include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <algorithm> #include <queue> #include <string> #include <set> #include <stack> #include <map> #include <cmath> #include <cstdlib> using namespace std; //LOOP #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FED(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) //STL #define PB push_back //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RS(s) scanf("%s", s) typedef long long LL; const int INF = 0x3f3f3f3f; const int MAXN = 1010; #define FF(i, a, b) for(int i = (a); i < (b); ++i) #define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i) #define CPY(a, b) memcpy(a, b, sizeof(a)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) #define EQ(a, b) (fabs((a) - (b)) <= 1e-10) #define ALL(c) (c).begin(), (c).end() #define SZ(V) (int)V.size() #define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p) #define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q) #define WI(n) printf("%d\n", n) #define WS(s) printf("%s\n", s) typedef vector <int> VI; typedef unsigned long long ULL; const double eps = 1e-10; const LL MOD = 1e9 + 7; const int maxn = 1010; int ipt[maxn][maxn]; int up[maxn][maxn], dwn[maxn][maxn], rht[maxn][maxn], lft[maxn][maxn]; int len[maxn], n, m; void update_col(int y) { FE(i, 1, n) if (ipt[i][y]) up[i][y] = up[i - 1][y] + 1; else up[i][y] = 0; FED(i, n, 1) if (ipt[i][y]) dwn[i][y] = dwn[i + 1][y] + 1; else dwn[i][y] = 0; } void update_row(int x) { FE(j, 1, m) if (ipt[x][j]) lft[x][j] = lft[x][j - 1] + 1; else lft[x][j] = 0; FED(j, m, 1) if (ipt[x][j]) rht[x][j] = rht[x][j + 1] + 1; else rht[x][j] = 0; } int solve(int sta, int hei, int con) { int lm = sta, rm = sta; int ans = 0; for (int h = hei; h >= 1; h--) { while (lm >= 1 && len[lm] >= h) lm--; while (rm <= con && len[rm] >= h) rm++; ans = max(ans, h * (rm - lm - 1)); } return ans; } int main() { //freopen("0.txt", "r", stdin); int q, x, y, op; cin >> n >> m >> q; FE(i, 1, n) FE(j, 1, m) RI(ipt[i][j]); FE(i, 1, n) update_row(i); FE(j, 1, m) update_col(j); while (q--) { RIII(op, x, y); if (op == 1) { ipt[x][y] ^= 1; update_row(x); update_col(y); // cout << "UP " << endl; // FE(i, 1, n) { // FE(j, 1, m) // cout << up[i][j] << ' '; // cout <<endl; // } // cout << "----" << endl; // cout << "right " << endl; // FE(i, 1, n) { // FE(j, 1, m) // cout << rht[i][j] << ' '; // cout <<endl; // } // cout << "----" << endl; } else { int ans = 0; FE(j, 1, m) len[j] = up[x][j]; ans = max(ans, solve(y, len[y], m)); FE(j, 1, m) len[j] = dwn[x][j]; ans = max(ans, solve(y, len[y], m)); FE(i, 1, n) len[i] = lft[i][y]; ans = max(ans, solve(x, len[x], n)); FE(i, 1, n) len[i] = rht[i][y]; ans = max(ans, solve(x, len[x], n)); WI(ans); } } return 0; }
以上就是codeforces248(div1) B Nanami's Digital Board的内容,更多相关内容请关注PHP中文网(m.sbmmt.com)!