题目描述
二维滑动窗口
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#define mod 998244353
using namespace std;
typedef long long ll;
int n,m,l,d;
int a[1010][1010];
int maxr[1010][1010];
int minr[1010][1010];
int maxc[1010][1010];
int minc[1010][1010];
int q[10010];
int main()
{
cin>>n>>m>>l>>d;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
//maxr
for(int i=1;i<=n;i++)//对每一行进行滑动窗口,大小为l,结果存储在maxr中
{
int hh=0,tt=-1;
for(int j=1;j<=m;j++)
{
while(hh<=tt&&a[i][q[tt]]<=a[i][j]) tt--;
q[++tt]=j;
while(hh<=tt&&q[hh]<j-d+1) hh++;
if(j>=d) maxr[i][j-d+1]=a[i][q[hh]];
}
}
//minr
for(int i=1;i<=n;i++)//对每一行进行滑动窗口,大小为l,结果存储在minr中
{
int hh=0,tt=-1;
for(int j=1;j<=m;j++)
{
while(hh<=tt&&a[i][q[tt]]>=a[i][j]) tt--;
q[++tt]=j;
while(hh<=tt&&q[hh]<j-d+1) hh++;
if(j>=d) minr[i][j-d+1]=a[i][q[hh]];
}
}
//maxc
for(int i=1;i<=m-d+1;i++)
{
int hh=0,tt=-1;
for(int j=1;j<=n;j++)
{
while(hh<=tt&&maxr[q[tt]][i]<=maxr[j][i]) tt--;
q[++tt]=j;
while(hh<=tt&&q[hh]<j-l+1) hh++;
if(j>=l) maxc[j-l+1][i]=maxr[q[hh]][i];
}
}
//minc
for(int i=1;i<=m-d+1;i++)
{
int hh=0,tt=-1;
for(int j=1;j<=n;j++)
{
while(hh<=tt&&minr[q[tt]][i]>=minr[j][i]) tt--;
q[++tt]=j;
while(hh<=tt&&q[hh]<j-l+1) hh++;
if(j>=l) minc[j-l+1][i]=minr[q[hh]][i];
}
}
ll res=0;
for(int i=1;i<=n-l+1;i++)
{
for(int j=1;j<=m-d+1;j++)
{
res=(res+(ll)maxc[i][j]*minc[i][j])%mod;
}
}
cout<<res;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla