[BZOJ1047][HAOI2007]单调队列在理想正方形问题中的应用与优化

 1 #include 
 2 using namespace std;
 3 int q[1005], c[1005][1005], r[4][1005][1005];
 4 int main()
 5 {
 6     int a, b, n, front, back, ans = 1000000000;
 7     scanf("%d%d%d", &a, &b, &n);
 8     for(int i = 1; i <= a; ++i)
 9         for(int j = 1; j <= b; ++j)
10             scanf("%d", &c[i][j]);
11     for(int i = 1; i <= a; ++i)
12     {
13         frOnt= back = 0;
14         for(int j = 1; j <= b; ++j)
15         {
16             if(front != back && j - q[front + 1] == n)
17                 ++front;
18             while(front != back && c[i][j] <= c[i][q[back]])
19                 --back;
20             q[++back] = j;
21             r[0][i][j] = c[i][q[front + 1]];
22         }
23         frOnt= back = 0;
24         for(int j = 1; j <= b; ++j)
25         {
26             if(front != back && j - q[front + 1] == n)
27                 ++front;
28             while(front != back && c[i][j] >= c[i][q[back]])
29                 --back;
30             q[++back] = j;
31             r[1][i][j] = c[i][q[front + 1]];
32         }
33     }
34     for(int j = n; j <= b; ++j)
35     {
36         frOnt= back = 0;
37         for(int i = 1; i <= a; ++i)
38         {
39             if(front != back && i - q[front + 1] == n)
40                 ++front;
41             while(front != back && r[0][i][j] <= r[0][q[back]][j])
42                 --back;
43             q[++back] = i;
44             r[2][i][j] = r[0][q[front + 1]][j];
45         }
46         frOnt= back = 0;
47         for(int i = 1; i <= a; ++i)
48         {
49             if(front != back && i - q[front + 1] == n)
50                 ++front;
51             while(front != back && r[1][i][j] >= r[1][q[back]][j])
52                 --back;
53             q[++back] = i;
54             r[3][i][j] = r[1][q[front + 1]][j];
55         }
56     }
57     for(int i = n; i <= a; ++i)
58         for(int j = n; j <= b; ++j)
59             ans = min(ans, r[3][i][j] - r[2][i][j]);
60     printf("%d\n", ans);
61     return 0;
62 }