单调队列——二维滑动窗口模型

P2216 理想的正方形

Ac的代码

#include <iostream>
using namespace std;
const int N = 1000+10;
int a,b,n;
int s[N][N],q[N],hh=0,tt=-1,d;
int anserA[N],anserB[N],anserC[N],anserD[N];

int rsMin[N][N],rsMax[N][N];

void get_max(int * p,int * f,int col){
  hh=0,tt=-1,d=0;
  for(int i=0;i<col;i++){
    if(i-n+1>q[hh]) hh++;
    while(hh<=tt&&p[q[tt]]<=p[i]) tt--;
    q[++tt] = i;
    if(i>=n-1) f[d++] = p[q[hh]];
  }
  f[N-1] = d;
}

void get_min(int * p,int * f,int col){
  hh=0,tt=-1,d=0;
  for(int i=0;i<col;i++){
    if(i-n+1>q[hh]) hh++;
    while(hh<=tt&&p[q[tt]]>=p[i]) tt--;
    q[++tt] = i;
    if(i>=n-1) f[d++] = p[q[hh]];
  }
  f[N-1] = d;
}

int main()
{
  cin>>a>>b>>n;

  for(int i=0;i<a;i++)
    for(int j=0;j<b;j++) cin>>s[i][j];
  //这一步之后，rsMax[i]存储每个正方形尝试的一条边的最大值，rsMin同理
  for(int i=0;i<a;i++){
    get_max(s[i],rsMax[i],b);
    get_min(s[i],rsMin[i],b);
  }
  

  int anser = 1e10; //取到最大
//二维区间求最值问题，从列开始考虑。即max{a,b,c,d} = max{max{a,b},max{c,d}}
  for(int i=0;i<rsMax[0][N-1];i++){
    //将一列的值存入临时数组anserA,anserB(最小值)
    for(int j=0;j<a;j++){
      anserA[j] = rsMax[j][i];
      anserB[j] = rsMin[j][i];
    }
  //将列的值也进行一次滑动窗口操作，这一步后anserC[i] 代表第i个正方形尝试的最大值,anserD也一样
    get_max(anserA,anserC,a);
    get_min(anserB,anserD,a);
    // cout << anserC[N-1] << endl;
  //到这里，我们已经将一个子矩阵一维化了，接下来套模板就完了
    for(int k=0;k<anserC[N-1];k++) {
      anser = min(anser,anserC[k]-anserD[k]);
    }
  }
  cout << anser;
  return 0;
}

折腾了一天才过（菜麻了)。acwing周赛开打了，等明天再整理下图文笔记8

超水的笔记（逃