1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
| #include <bits/stdc++.h> #define N 4000005 using namespace std;
template <typename T> inline void read(T &num) { T x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * f; }
int n, m, Q; int len[N<<2], q1[N], q2[N]; vector<int> A[N]; int lm[N<<2], rm[N<<2], val[N<<2];
inline int o(int x, int y) { return x*m+y; }
inline void merge(int ind, int ls, int rs) { int h1 = 1, h2 = 1, t1 = 0, t2 = 0; for (int r = 1, l = 1; r <= m; r++) { while (h1 <= t1 && rm[o(ls,q1[t1])] > rm[o(ls,r)]) t1--; q1[++t1] = r; while (h2 <= t2 && lm[o(rs,q2[t2])] > lm[o(rs,r)]) t2--; q2[++t2] = r; while (h1 <= t1 && h2 <= t2 && rm[o(ls,q1[h1])] + lm[o(rs,q2[h2])] < r-l+1) { if (q1[h1] == l) h1++; if (q2[h2] == l) h2++; l++; } val[o(ind,r)] = max(max(val[o(ls,r)], val[o(rs,r)]), r-l+1); } for (int i = 1; i <= m; i++) lm[o(ind,i)] = lm[o(ls,i)] + (lm[o(ls,i)]==len[ls]?lm[o(rs,i)]:0); for (int i = 1; i <= m; i++) rm[o(ind,i)] = rm[o(rs,i)] + (rm[o(rs,i)]==len[rs]?rm[o(ls,i)]:0); } void build(int ind, int l, int r) { len[ind] = r-l+1; if (l == r) { for (int i = 1; i <= m; i++) lm[o(ind,i)] = rm[o(ind,i)] = val[o(ind,i)] = A[l][i]; return; } int mid = (l + r) >> 1; build(ind<<1, l, mid); build(ind<<1|1, mid+1, r); merge(ind, ind<<1, ind<<1|1); } void update(int ind, int l, int r, int x, int y, int v) { if (l == r) { lm[o(ind,y)] = rm[o(ind,y)] = val[o(ind,y)] = v; return; } int mid = (l + r) >> 1; if (x <= mid) update(ind<<1, l, mid, x, y, v); else update(ind<<1|1, mid+1, r, x, y, v); merge(ind, ind<<1, ind<<1|1); }
void query(int ind, int l, int r, int x, int y) { int ret = 0; if (x <= l && r <= y) { merge(0, 0, ind); return; } int mid = (l + r) >> 1; if (x <= mid) query(ind<<1, l, mid, x, y); if (mid < y) query(ind<<1|1, mid+1, r, x, y); }
int main() { read(n); read(m); read(Q); for (int i = 1; i <= n; i++) A[i].resize(m+1); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { read(A[i][j]); } build(1, 1, n); for (int i = 1, tp, x, y, a, b; i <= Q; i++) { read(tp); if (tp == 0) { read(x); read(y); if (A[x][y]) update(1, 1, n, x, y, 0); else update(1, 1, n, x, y, 1); A[x][y] = 1 - A[x][y]; } else { read(x); read(y); read(a); read(b); for (int j = 1; j <= m; j++) { lm[o(0,j)] = rm[o(0,j)] = val[o(0,j)] = 0; } query(1, 1, n, x, a); int ans = 0; for (int j = y; j <= b; j++) { ans = max(ans, min(j-y+1, val[o(0, j)])); } printf("%d\n", ans); } } return 0; }
|