Description：

给一个 $n\times m$ 的 $01$ 矩阵，支持单点修改，查询子矩阵内最大全 $0$ 正方形。

$1\leqslant n\times m\leqslant 10^6,n\geqslant m,q\leqslant 10^3$

Solution：

看上去 $q$ 很小， $m$ 也很小，因此只要 $qm\log n$ 的复杂度就可以通过。

首先我们知道如果信息可以合并，那么就可以用线段树来维护，考虑怎么用线段树来维护这个。

对 $n$ 这一维建立线段树，先考虑一个弱化版的弱化版，无修改全局最大全 $0$ 正方形，由于线段树的本质是分治，我们也可以类似的考虑经过分治中点的最大全 $0$ 正方形，于是我们就需要在线段树节点上维护每一行左右的最长全零前缀和后缀，然后用双指针，枚举 $bot$ 从上往下扫，另一个 $top$ 指针随之移动，正方形的限制太强，我们可以计算矩形，对于每个矩形，显然都可以包括一个长度为宽的正方形，那么我们就可以在双指针扫的时候同时维护一个单调队列用于求两个指针之间的两侧的最大值，也就是得到了这个矩形在上面为 $top$ 下面为 $bot$ 时的最大的宽，然后有一个技巧就是始终保持矩形的高小于等于宽，可以发现这样一定不会漏解，因为已经让下边界为 $bot$ 时长和宽尽量接近了，如果某一个再变小都会使答案变劣，或者在上面已经统计，因此我们就可以计算出跨过中点的最大的正方形，修改也很好说，直接递归进叶节点修改就行了。

然后考虑怎么查询子矩阵最大正方形，首先左右端点可以用线段树区间来限制，难的是上下怎么限制，我们可以在合并的时候在 $bot$ 位于每个位置的时候记录一个 $d[i]$ 表示在 $bot=i$ 时高最大是多少，然后发现实际上答案就是： $$ \max(\min(Top-i,d[i])) $$ 于是我们可以再用线段树维护一个 $d$ 的最大值，然后每次 $O(m)$ 计算一下答案即可。

注意在合并区间的时候一定不能把一个特别大的结构体当参数传进去，不然特别慢，最好的方法是只传下标。

Code：

// luogu-judger-enable-o2

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

    register int res = 0,f = 1;

    register char c = getchar();

    while(!isdigit(c))

    {

        if(c == '-')f = -1;

        c = getchar();

    }

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res * f;

}

#define MAXN 4000010

#define I inline

int n,m,q;

int L[MAXN * 2],R[MAXN * 2],D[MAXN * 2];

int id(int pos,int v){return pos * m + v;}

struct node

{

    int lc,rc;

    int siz;

}t[MAXN << 1];

int ptr = 0;

I int newnode(){return ++ptr;}

int ans,tmp;

int root;

#define mid ((l + r) >> 1)

int ql[MAXN],hl,tl;

int qr[MAXN],hr,tr;

I void merge(int rt,int lc,int rc)

{

    hl = hr = 1;tl = tr = 0;

    for(int bot = 1,top = 1;bot <= m;++bot)

    {

        L[id(rt,bot)] = (L[id(lc,bot)] == t[lc].siz ? t[lc].siz + L[id(rc,bot)] : L[id(lc,bot)]);

        R[id(rt,bot)] = (R[id(rc,bot)] == t[rc].siz ? t[rc].siz + R[id(lc,bot)] : R[id(rc,bot)]);

        while(hl <= tl && R[id(lc,ql[tl])] >= R[id(lc,bot)])--tl;

        ql[++tl] = bot;

        while(hr <= tr && L[id(rc,qr[tr])] >= L[id(rc,bot)])--tr;

        qr[++tr] = bot;

        while(hl <= tl && hr <= tr && bot - top + 1 > R[id(lc,ql[hl])] + L[id(rc,qr[hr])])

        {

            ++top;

            if(ql[hl] < top)++hl;

            if(qr[hr] < top)++hr;

        }

        D[id(rt,bot)] = bot - top + 1;

        D[id(rt,bot)] = max(D[id(rt,bot)],max(D[id(lc,bot)],D[id(rc,bot)]));

    }

    return;

} 

double tot3 = 0;

I void build(int &rt,int l,int r)

{

    rt = newnode();

    t[rt].siz = r - l + 1;

    if(l == r)

    {

        for(int p = 1;p <= m;++p)

        {

            L[id(rt,p)] = R[id(rt,p)] = D[id(rt,p)] = rd();

        }

        return;

    }

    build(t[rt].lc,l,mid);

    build(t[rt].rc,mid + 1,r);

    merge(rt,t[rt].lc,t[rt].rc);

    return;

}

void change(int rt,int p,int k,int l,int r)

{

    if(l == r)

    {

        L[id(rt,k)] ^= 1;R[id(rt,k)] ^= 1;D[id(rt,k)] ^= 1;

        return;

    }

    if(p <= mid)change(t[rt].lc,p,k,l,mid);

    else change(t[rt].rc,p,k,mid + 1,r);

    merge(rt,t[rt].lc,t[rt].rc);

    return;

}

int tag;

void cp(int a,int b)

{

    for(int i = 1;i <= m;++i)

    {

        L[id(a,i)] = L[id(b,i)];

        R[id(a,i)] = R[id(b,i)];

        D[id(a,i)] = D[id(b,i)];

    }

    return;

}

void query(int rt,int L,int R,int l,int r)

{

    if(L <= l && r <= R)

    {

        if(tag == -1)cp(ans,rt),tag = 0;

        else cp(tmp,ans),merge(ans,tmp,rt);

        return;

    }

    if(L <= mid)query(t[rt].lc,L,R,l,mid);

    if(R > mid)query(t[rt].rc,L,R,mid + 1,r);

    return;

}

int calc(int r1,int r2,int c1,int c2)

{

    tag = -1;

    query(root,r1,r2,1,n);

    int res = 0;

    for(int i = 1;i <= c2;++i)res = max(res,min(i - c1 + 1,D[id(ans,i)]));

    return res;

}

int main()

{

    scanf("%d%d%d",&n,&m,&q);

    build(root,1,n);

    ans = newnode();tmp = newnode();

    register int opt,x,y,r1,c1,r2,c2;

    for(register int i = 1;i <= q;++i)

    {

        opt = rd();

        if(opt == 0)

        {

            x = rd();y = rd();

            change(root,x,y,1,n);

        }

        else

        {

            r1 = rd();c1 = rd();r2 = rd();c2 = rd();

            printf("%d\n",calc(r1,r2,c1,c2));

        }

    }

    return 0;

}