题意:n*m的矩阵，有一些点不能选。k次操作，每次都让一个点变成不可选，每次都问当前可选的最大正方形。n,m,k<=2000

我想到了一个方法。过掉了。

新加的点造成的新的正方形一定过那个点，也就一定过它所在的列。

用第j列更新答案时，从当前答案+1开始从小到大试。 由于答案最多增加n次，所以总的尝试次数是O(N+K)的。 每次检验，我们从上到下枚举区间，用单调队列维护当前两边的最小值，时间是O(N)的。 所以总时间O(N^2+NK)

(看了cf的官方题解，没看懂，但时间是nklogk的)

但如果是求矩形最大面积怎么做呢？！！(或许不可做？)

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

void chmax(int &x,int y)
{
    if(x<y)x=y;
}
#define N 2010
int l[N][N],r[N][N];//水平上延伸的极限点
bool ok[N][N];//可用的点 
int now;
bool open;
int n,m,k,len,i,j;
void dp_lr(int i)//dp第i行的l,r 
{
    for (j=1;j<=m;++j)
    if (ok[i][j])
     l[i][j]=l[i][j-1];
    for (j=m;j;--j)
    if (ok[i][j])
     r[i][j]=r[i][j+1]; 
}

struct queue
{
    int q[N],h[N],head,tail;
    void clear()
    {
       head=1;tail=0;
    }
    void push(int x)
    {
        while (tail>=head&&h[tail]>=x) --tail;
        ++tail;
        q[tail]=i;h[tail]=x;
    }
    int len()
    {
        while (i-q[head]>now) ++head;
        if (h[head]<0) return -N;
        return h[head];
    }
}ql,qr;
void dp_ud(int j)//第j列更新当前答案 
{
    for (;;)
    {
        ql.clear();qr.clear();
        for (i=1;i<=now;++i) 
        {
            ql.push(j-l[i][j]);
            qr.push(r[i][j]-j);
        }
        for (;i<=n;++i)
        {
            ql.push(j-l[i][j]);
            qr.push(r[i][j]-j);
            if (ql.len()+qr.len()>=now) break;
        }
        if (i>n) return ;
        ++now;
    }
}

char ch[N]; 

int o;
struct query
{
    int x,y,ans;
    void init()
    {
        scanf("%d%d",&x,&y);
        ok[x][y]=0;l[x][y]=y+1;r[x][y]=y-1;
    }
    void add()
    {
        ans=now;
        ok[x][y]=1;
        dp_lr(x);
        dp_ud(y);
    }
}p[N];

int main()
{ freopen("1.in","r",stdin);freopen("1.out","w",stdout); 
   while (scanf("%d%d%d",&n,&m,&k)!=EOF)
   {
    int i,j;now=0;
    for (i=1;i<=n;++i)
    {
        scanf("%s",ch+1);
        for (j=1;j<=m;++j) 
        if(ch[j]=='.') ok[i][j]=1;
        else { ok[i][j]=0;l[i][j]=j+1;r[i][j]=j-1; }
    }
    for (i=1;i<=k;++i) p[i].init();

    for (i=1;i<=n;++i) {l[i][0]=1;r[i][m+1]=m;dp_lr(i);}
    for (j=1;j<=m;++j) dp_ud(j);

    for (i=k;i;--i) 
     p[i].add();
    for (i=1;i<=k;++i) printf("%d\n",p[i].ans);
   }
}