Codeforces Round #248 Div. 2 D. Nanami's Digital Board

題目鏈接：http://codeforces.com/contest/433/problem/D

題意

首先輸入n，m，q，表示n×m的01矩陣，有q次查詢
有兩種操作

• 1 x y表示(x,y)點的狀態取反
• 2 x y表示查詢(x,y)所在的由1組成的矩形的最大面積{(x,y)點在矩形的邊上}

解法

預處理u[x][y],d[x][y],l[x][y],r[x][y]
分別表示(x,y)向上，向下，向左，向右有多少各連續的1
每層查詢分別枚舉四個方向，統計最大值即可

const int N=1005;
int a[N][N];
int u[N][N],dow[N][N],l[N][N],r[N][N];
int n,m,q;
int heigh[N];
void init() {
    memset(u,0,sizeof(u));
    memset(dow,0,sizeof(dow));
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
}
void update_raw(int x) {
    for(int i=1;i<=m;i++) {
        if(a[x][i]) l[x][i]=l[x][i-1]+1;
        else l[x][i]=0;
    }
    for(int i=m;i>0;i--) {
        if(a[x][i]) r[x][i]=r[x][i+1]+1;
        else r[x][i]=0;
    }
}

void update_col(int y) {
    for(int i=1;i<=n;i++) {
        if(a[i][y]) u[i][y]=u[i-1][y]+1;
        else u[i][y]=0;
    }
    for(int i=n;i>0;i--) {
        if(a[i][y]) dow[i][y]=dow[i+1][y]+1;
        else dow[i][y]=0;
    }
}
int getmax(int x,int h,int lim) {
    int res=0;
    int lm=x;
    int rm=x;
    for(int i=h;i>0;i--) {
        while(lm>0&&heigh[lm]>=i) lm--;
        while(rm<=lim&&heigh[rm]>=i) rm++;
        res=max(res,i*(rm-lm-1));
    }
    return res;
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    while(cin>>n>>m>>q) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                cin>>a[i][j];
            }
        }
        init();
        for(int i=1;i<=n;i++) {
            update_raw(i);
        }
        for(int i=1;i<=m;i++) {
            update_col(i);
        }

        int op,x,y;
        while(q--) {
            cin>>op>>x>>y;
            if(op==1) {
                a[x][y]^=1;
                update_raw(x);
                update_col(y);
            }else {
                int ans=0;
                for(int i=1;i<=n;i++) heigh[i]=l[i][y];
                ans=max(ans,getmax(x,heigh[x],n));

                for(int i=1;i<=n;i++) heigh[i]=r[i][y];
                ans=max(ans,getmax(x,heigh[x],n));

                for(int i=1;i<=m;i++) heigh[i]=u[x][i];
                ans=max(ans,getmax(y,heigh[y],m));

                for(int i=1;i<=m;i++) heigh[i]=dow[x][i];
                ans=max(ans,getmax(y,heigh[y],m));

                cout<<ans<<endl;
            }
        }
    }
    return 0;
}