[洛谷P2216]理想的正方形

        本题目为矩阵最值问题的模板题

---

难度：提高+/省选-

题目描述

        有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入输出格式

输入格式：

        第一行为3个整数，分别表示a,b,n的值
        第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式：

        仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例

Sample input

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

Sampe output

1

说明

问题规模

1. 矩阵中的所有数都不超过1,000,000,000

2. 20%的数据2≤a,b≤100,n≤a,n≤b,n≤10

3. 100%的数据2≤a,b≤1000,n≤a,n≤b,n≤100

题解

        这是一道很好的矩阵最值问题。下面介绍3种方法。

• 暴力DP法（不能AC）
          如果用dp(x，y，k)表示以坐标(x，y)为左上方点，边长为k的方阵最大值，显然有状态转移方程（最小值类比）：

  $$dp(x,y,k)=\max\{dp(x+1,y,k-1),dp(x,y+1,k-1),dp(x+1,y+1,k-1)\}$$

          这种思想即是将大方阵分成了三个小方阵，并且这三个小方阵可以覆盖原来的大方阵。按照该方程递推，即可以得出答案。时间复杂度O(abn)，预计得分60，开O2优化可以AC。
          三维数组过大会爆空间，需要滚动数组优化。

  #include<iostream>
  #include<cstdio>
  #include<cstring>
  
  #define MAX 1000
  using namespace std;
  unsigned int op[MAX][MAX], a, b, n, dpMax[MAX][MAX][2], dpMin[MAX][MAX][2];
  bool key = false;
  
  int read() {
      char e = getchar();
      while (e < '0' || e > '9')e = getchar();
      int s = 0;
      while (e >= '0' && e <= '9') {
          s = s * 10 + e - '0';
          e = getchar();
      }
      return s;
  }
  
  int main() {
      a = read(), b = read(), n = read();
      memset(dpMax, 0, sizeof(dpMax)), memset(dpMin, -1, sizeof(dpMin));
      for (int i = 0; i < a; i++) {
          for (int j = 0; j < b; j++)op[i][j] = read();
      }
      unsigned int ans = dpMin[0][0][0];
      for (int k = 1; k <= n; k++) {
          for (int i = a - k; i >= 0; i--) {
              for (int j = b - k; j >= 0; j--) {
                  if (k == 1)dpMax[i][j][key] = dpMin[i][j][key] = op[i][j];
                  else {
                      dpMax[i][j][key] = max(op[i][j], max(dpMax[i + 1][j][!key],max(dpMax[i][j + 1][!key], dpMax[i + 1][j + 1][!key])));
                      dpMin[i][j][key] = min(op[i][j], min(dpMin[i + 1][j][!key],min(dpMin[i][j + 1][!key], dpMin[i + 1][j + 1][!key])));
                  }
                  if (k == n)ans = min(ans, dpMax[i][j][key] - dpMin[i][j][key]);
              }
          }
          key = !key;
      }
      cout << ans;
      return 0;
  }

• 倍增DP法（二维ST表）
          之前的日志记录了一维ST表。建立ST表是一种基于倍增思想的求区间最值方法，本质上是DP。这里将一维ST表推广到二维。
          令ST(x，y，k)表示以坐标(x，y)为左上方点，边长为2^k的方阵的最大值。那么有状态转移方程：

  $$ST(x,y,k)=\max\{ST(x,y,k),ST(x+bin(k-1),y,k-1),ST(x,y+bin(k-1),k-1),ST(x+bin(k-1),y+bin(k-1),k-1)\}$$

          方程容易理解，这里是将大方阵分成四个等大的小方阵，它们彼此没有交集但覆盖了整个大方阵。根据方程递推即可，重点在于如何用ST表求边长为n的方阵最大值。
          根据一维ST表，应将方阵化为四个小方阵。容易得出边长为n的方阵最值即为：

  $$\max\{ST(x,y,log(n)),ST(x+n-bin(log(n)),y,log(n)),ST(x,y+n-bin(log(n)),log(n)),ST(x+n-bin(log(n)),y+n-bin(log(n)),log(n))\}$$

          log以及bin与一维ST表相同，详见一维ST表。
          最小值类比。时间复杂度O(ablog(n))。

  #include<iostream>
  #include<cstdio>
  
  #define MAX 1000
  using namespace std;
  int a, b, n, op[MAX][MAX], ST1[MAX][MAX][10], ST2[MAX][MAX][10];
  int bin[10], log[101];
  
  inline int read() {//读入优化
      char e = getchar();
      while (e < '0' || e > '9')e = getchar();
      int s = 0;
      while (e >= '0' && e <= '9') {
          s = s * 10 + e - '0';
          e = getchar();
      }
      return s;
  }
  
  int main() {
      a = read(), b = read(), n = read();
      for (int i = 0; i < a; i++)
          for (int j = 0; j < b; j++) {
              op[i][j] = read();
              ST1[i][j][0] = ST2[i][j][0] = op[i][j];
          }
      log[0] = -1, bin[0] = 1;
      for (int i = 1; i <= 100; i++)log[i] = log[i / 2] + 1;//log
      for (int i = 1; i < 10; i++)bin[i] = bin[i - 1] * 2;//bin
      for (int k = 1; k <= log[n]; k++) {
          for (int i = 0; i < a; i++) {
              for (int j = 0; j < b; j++) {
                  if (i + bin[k] > a || j + bin[k] > b)continue;
                  ST1[i][j][k] = max(ST1[i][j][k - 1],max(ST1[i + bin[k - 1]][j][k - 1],max(ST1[i][j + bin[k - 1]][k - 1], ST1[i + bin[k - 1]][j + bin[k - 1]][k - 1])));
                  ST2[i][j][k] = min(ST2[i][j][k - 1],min(ST2[i + bin[k - 1]][j][k - 1],min(ST2[i][j + bin[k - 1]][k - 1], ST2[i + bin[k - 1]][j + bin[k - 1]][k - 1])));
              }
          }
      }
      int ans = 0x7fffffff;
      for (int i = 0; i <= a - n; i++) {
          for (int j = 0; j <= b - n; j++) {
              int maxn = max(ST1[i][j][log[n]],max(ST1[i + n - bin[log[n]]][j][log[n]],max(ST1[i][j + n - bin[log[n]]][log[n]],ST1[i + n - bin[log[n]]][j + n - bin[log[n]]][log[n]])));
              int minn = min(ST2[i][j][log[n]],min(ST2[i + n - bin[log[n]]][j][log[n]],min(ST2[i][j + n - bin[log[n]]][log[n]],ST2[i + n - bin[log[n]]][j + n - bin[log[n]]][log[n]])));
              ans = min(ans, maxn - minn);
          }
      }
      cout << ans;
      return 0;
  }

• 单调队列法
          单调队列可以维护固定长度的区间最值，可以用单调队列维护每一行长度为n的所有区间最值，由此可以得到一个二维表(行数为a，列数为b-n+1)。在这个二维表上再用单调队列维护每一列长度为n的所有区间最值，又可以得到一个二维表(行数为a-n+1，列数为b-n+1)，它记录的即是所有边长为n的方阵的最值。
          单调队列维护固定区间最值详见这篇日志。

  #include<iostream>
  #include<deque>
  #include<cstdio>
  
  #define MAX 1000
  using namespace std;
  deque<int> q1, q2;
  int a, b, n, op[MAX][MAX], X[MAX][MAX], x[MAX][MAX], Y[MAX][MAX], y[MAX][MAX];
  
  inline int read() {
      char e = getchar();
      while (e < '0' || e > '9')e = getchar();
      int s = 0;
      while (e >= '0' && e <= '9') {
          s = s * 10 + e - '0';
          e = getchar();
      }
      return s;
  }
  
  inline void push1(int x, int y) {//单调增队列
      while (!q1.empty() && op[x][q1.back()] < op[x][y])q1.pop_back();
      q1.push_back(y);
  }
  
  inline void push2(int x, int y) {//单调减队列
      while (!q2.empty() && op[x][q2.back()] > op[x][y])q2.pop_back();
      q2.push_back(y);
  }
  
  inline void push3(int x, int y) {
      while (!q1.empty() && X[q1.back()][y] < X[x][y])q1.pop_back();
      q1.push_back(x);
  }
  
  inline void push4(int x0, int y0) {
      while (!q2.empty() && x[q2.back()][y0] > x[x0][y0])q2.pop_back();
      q2.push_back(x0);
  }
  
  inline int front1(int x) {
      while (q1.front() <= x)q1.pop_front();
      return q1.front();
  }
  
  inline int front2(int x) {
      while (q2.front() <= x)q2.pop_front();
      return q2.front();
  }
  
  int main() {
      a = read(), b = read(), n = read();
      for (int i = 0; i < a; i++)
          for (int j = 0; j < b; j++)op[i][j] = read();
      for (int i = 0; i < a; i++) {
          q1.clear(), q2.clear();
          for (int j = 0; j < n; j++)push1(i, j), push2(i, j);
          X[i][0] = op[i][front1(-1)], x[i][0] = op[i][front2(-1)];
          for (int poi = 1, j = n; j < b; j++, poi++)
              push1(i, j), push2(i, j), X[i][poi] = op[i][front1(j - n)], x[i][poi] = op[i][front2(j - n)];
      }
      for (int i = 0; i <= b - n; i++) {
          q1.clear(), q2.clear();
          for (int j = 0; j < n; j++)push3(j, i), push4(j, i);
          Y[i][0] = X[front1(-1)][i], y[i][0] = x[front2(-1)][i];
          for (int poi = 1, j = n; j < a; j++, poi++)
              push3(j, i), push4(j, i), Y[i][poi] = X[front1(j - n)][i], y[i][poi] = x[front2(j - n)][i];
      }
      int ans = 0x7fffffff;
      for (int i = 0; i <= b - n; i++) {
          for (int j = 0; j <= a - n; j++)ans = min(ans, Y[i][j] - y[i][j]);
      }
      cout << ans;
      return 0;
  }