C++11(clang++ 3.9) 解法, 执行用时: 54ms, 内存消耗: 7784K, 提交时间: 2019-01-07 18:01:02

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cassert>
#include <map>
using namespace std;
#define RG register
#define IL __inline__ __attribute__((always_inline))
#define For(i, a, b) for(RG int i = a, ___u = b; i <= ___u; ++i)
#define Dor(i, a, b) for(RG int i = b, ___d = a; i >= ___d; --i)
#define Rep(i, a, b) for(RG int i = a, ___u = b; i != ___u; ++i)
#define dmin(a, b) ((a) < (b) ? (a) : (b))
#define dmax(a, b) ((a) > (b) ? (a) : (b))
#define cmin(a, b) ((a) > (b) ? (a) = (b), 1 : 0)
#define cmax(a, b) ((a) < (b) ? (a) = (b), 1 : 0)
#define diff(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define dabs(i) ((i) > 0 ? (i) : -(i))
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef long double ld;

#include <set>

namespace pb_ds
{   
 // 输入输出优化模板从此开始
 namespace io
 {
  const int MaxBuff = 1 << 20;
  const int Output = 1 << 24;
  char B[MaxBuff], *S = B, *T = B;
  //#define getc() getchar()
  #define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
  char Out[Output], *iter = Out;
  IL void flush()
  {
   fwrite(Out, 1, iter - Out, stdout);
   iter = Out;
  }
 }
 
 template<class Type> IL Type read()
 {
  using namespace io;
  RG char ch; RG Type ans = 0; RG bool neg = 0;
  while(ch = getc(), (ch < '0' || ch > '9') && ch != '-')  ;
  ch == '-' ? neg = 1 : ans = ch - '0';
  while(ch = getc(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
  return neg ? -ans : ans;
 }
 template<class Type> IL void print(RG Type x, RG char ch = '\n')
 {
  using namespace io;
  if(!x) *iter++ = '0';
  else
  {
   if(x < 0) *iter++ = '-', x = -x;
   static int S2[100]; RG int t = 0;
   while(x) S2[++t] = x % 10, x /= 10;
   while(t) *iter++ = '0' + S2[t--];
  }
  *iter++ = ch;
 }
 // 输入输出优化模板到此结束
 
 const int MaxN = 2010;
 const int MaxS = MaxN * MaxN;
 
 int int_mem[MaxS * 7 + MaxN], *int_tot = int_mem;
 int *map[MaxS];
 int N, M;
 
 typedef const int * const cintarr;

 
 int *__val__;
  
 int qp, ql, qr, qs, qt, qans, qmans;
 
 struct Data{int v, p;} lq[MaxN], rq[MaxN];
 IL void calc_val(RG const int m, RG cintarr L, RG cintarr R, RG int* const val = __val__)
 {
  if(!L || !R) // leaf
  {
   memcpy(val + qs, map[m] + qs, (qt - qs + 1) << 2);
   return;
  }
  RG const int lmax = m - ql + 1, rmax = qr - m;
  RG int lh = 1, lt = 0, rh = 1, rt = 0, k = qs - 1;
  RG Data d;
  For(i, qs, qt)
  {
   d = (Data) {dmin(lmax, L[i]), i}; while(lh <= lt && lq[lt].v >= d.v) --lt; lq[++lt] = d;
   d = (Data) {dmin(rmax, R[i]), i}; while(rh <= rt && rq[rt].v >= d.v) --rt; rq[++rt] = d;
   while(k != i && i - k > lq[lh].v + rq[rh].v)
   {
    ++k;
    (lq[lh].p == k) ? ++lh : 0;
    (rq[rh].p == k) ? ++rh : 0;
   }
   val[i] = i - k;
  }
 }
 #define cmaxmax(a, b, c) ((b) > (c) ? cmax(a, b) : cmax(a, c))
 #define cmaxmin(a, b, c) ((b) < (c) ? cmax(a, b) : cmax(a, c))
 IL void query_val(RG cintarr val = __val__)
 {
  For(i, qs, qt) cmaxmin(qans, val[i], i - qs + 1);
 }
 
 struct SNode *tot;
 struct SNode
 {
  int l, r, m;
  int *lval, *rval, *val, max_ans;
  SNode *pl, *pr;
  
  IL void save()
  {
   calc_val(m, pl ? pl->rval : 0, pr ? pr->lval : 0, val);
   qans = (l != r ? dmax(pl->max_ans, pr->max_ans) : 0); 
   query_val(val); max_ans = qans;
   if(l == r)
   {
    memcpy(lval + 1, val + 1, M << 2);
    memcpy(rval + 1, val + 1, M << 2);
    return;
   }
   RG int lmax = m - l + 1, rmax = r - m;
   RG cintarr pll = pl->lval, plr = pl->rval, plv = pl->val;
   RG cintarr prl = pr->lval, prr = pr->rval, prv = pr->val;
   For(i, 1, M)
   {
    cmaxmax(val[i], plv[i], prv[i]);
    lval[i] = (pll[i] == lmax ? lmax + prl[i] : pll[i]);
    rval[i] = (prr[i] == rmax ? rmax + plr[i] : prr[i]);
   }
  }
  
  void build(RG int _l = 1, RG int _r = N)
  {
   l = _l, r = _r, m = (l + r) >> 1;
   lval = int_tot; int_tot += M;
   rval = int_tot; int_tot += M;
   val = int_tot; int_tot += M;
   if(l != r)
   {
    (pl = ++tot)->build(l, m);
    (pr = ++tot)->build(m + 1, r);
   }
   save();
  }
  void modify()
  {
   (l != r) ? (qp <= m ? pl : pr)->modify() : void(0); 
   save();
  }
  void query()
  {
   if(ql <= l && r <= qr)
    return query_val(val);
   (ql <= m && m < qr) 
    ? (calc_val(m, pl->rval, pr->lval), query_val())
    : void(0);
   #define PLQ (ql <= m && qans < dmin(qmans, pl->max_ans) ? pl->query() : void(0))
   #define PRQ (m <  qr && qans < dmin(qmans, pr->max_ans) ? pr->query() : void(0))
   (pl->max_ans > pr->max_ans) ? (PLQ, PRQ) : (PRQ, PLQ);
  }
 } mem[MaxS * 2];
 
 
 IL void main()
 {
  RG int (*F)() = read<int>;
  N = F(), M = F();
  RG int Q = F();
  __val__ = int_tot;
  int_tot += M;
  For(i, 1, N) 
  {
   map[i] = int_tot;
   int_tot += M;
   For(j, 1, M) map[i][j] = F();
  }
  RG SNode *T = tot = mem;
  qs = 1;
  qt = M;
  ql = 1;
  qr = N;
  T->build();
  
  while(Q--)
   if(F()) // query
   {
    ql = F();
    qs = F();
    qr = F();
    qt = F();
    qans = 0;
    qmans = dmin(qr - ql + 1, qt - qs + 1);
    T->query();
    print(qans);
   }
   else // mod
   {
    qp = F();
    map[qp][F()] ^= 1;
    qs = 1;
    qt = M;
    ql = 1;
    qr = N;
    T->modify();
   }
  io::flush();
 }
}

int main()
{
 pb_ds::main();
 fclose(stdin), fclose(stdout);  
}