CF 480 E. Parking Lot

http://codeforces.com/contest/480/problem/E
题意：
　　给一个n*m的01矩阵，每次可以将一个0修改为1，求最大全0的矩阵。
分析：
　　将询问离线，从后往前处理询问，相当于每次将一个1变成0，答案是递增的。
　　用悬线法或者单调栈来求。
代码：
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 using namespace std;
12 typedef long long LL;
13 
14 inline int read() {
15     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
16     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
17 }
18 
19 const int N = 2010;
20 
21 char a[N][N];
22 int x[N], y[N], L[N], R[N], U[N][N], D[N][N], q1[N], q2[N], ans[N], sk[N];
23 int Ans, n, m;
24 
25 void solve() {
26     for (int i=1; i<=n; ++i) 
27         for (int j=1; j<=m; ++j) 
28             U[i][j] = a[i][j] == '.' ? U[i-1][j] + 1 : 0;
29     for (int i=n; i>=1; --i) 
30         for (int j=1; j<=m; ++j) 
31             D[i][j] = a[i][j] == '.' ? D[i+1][j] + 1 : 0;
32     for (int i=1; i<=n; ++i) { // 单调栈 
33         U[i][0] = U[i][m+1] = -1;
34         for (int top=0,j=1; j<=m+1; ++j) {
35             while (top > 0 && U[i][j] < U[i][sk[top]]) R[sk[top]] = j, top--;
36             sk[++top] = j;
37         }
38         for (int top=0,j=m; j>=0; --j) {
39             while (top > 0 && U[i][j] < U[i][sk[top]]) L[sk[top]] = j, top --;
40             sk[++top] = j;
41         }
42         for (int j=1; j<=m; ++j) 
43             Ans = max(Ans, min(U[i][j], R[j] - L[j] - 1));
44     }
45     /*memset(R, 0x3f, sizeof(R)); // 悬线法 
46     for (int i=1; i<=n; ++i) {
47         int last = 0; 
48         for (int j=1; j<=m; ++j) {
49             if (a[i][j] == '.') L[j] = max(L[j], last + 1);
50             else last = j, L[j] = 0;
51         }
52         last = m + 1;
53         for (int j=m; j>=1; --j) {
54             if (a[i][j] == '.') R[j] = min(R[j], last - 1);
55             else last = j, R[j] = m + 1;
56         }
57         for (int j=1; j<=m; ++j) 
58             Ans = max(Ans, min(U[i][j], R[j] - L[j] + 1));
59     }*/
60 }
61 bool update(int x,int k) { // 判断能否组成k*k的方阵 
62     int L1 = 1, R1 = 0, L2 = 1, R2 = 0;
63     for (int j=1; j<=m; ++j) {
64         while (L1 <= R1 && j - q1[L1] + 1 > k) L1 ++;
65         while (L1 <= R1 && U[x][q1[R1]] >= U[x][j]) R1 --;
66         q1[++R1] = j;
67         
68         while (L2 <= R2 && j - q2[L2] + 1 > k) L2 ++;
69         while (L2 <= R2 && D[x][q2[R2]] >= D[x][j]) R2 --;
70         q2[++R2] = j;
71         
72         if (j >= k && U[x][q1[L1]] + D[x][q2[L2]] - 1 >= k) {
73             Ans = k;
74             return true;
75         }
76     }
77     return false;
78 }
79 void Change(int x,int y) {
80     a[x][y] = '.';
81     for (int i=x; i<=n; ++i) U[i][y] = a[i][y] == '.' ? U[i-1][y] + 1 : 0;
82     for (int i=x; i>=1; --i) D[i][y] = a[i][y] == '.' ? D[i+1][y] + 1 : 0;
83 }
84 int main() {
85     n = read(), m = read(); int Q = read();
86     for (int i=1; i<=n; ++i) scanf("%s",a[i]+1);
87     for (int i=1; i<=Q; ++i) {
88         x[i] = read(),y[i] = read();
89         a[x[i]][y[i]] = 'X';
90     }
91     solve();
92     for (int i=Q; i>=1; --i) {
93         ans[i] = Ans;
94         Change(x[i], y[i]);
95         while (update(x[i], Ans + 1));
96     }
97     for (int i=1; i<=Q; ++i) printf("%d
",ans[i]);
98     return 0;
99 }