#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010, mod = 998244353;
int n, m, a, b;
int resmn1[N][N], resmx1[N][N], resmn2[N][N], resmx2[N][N];
int g[N][N];
bool cmp(int a, int b, bool flag)
{
if(flag)return a <= b;
else return a >= b;
}
void get_r(bool flag, int res[][N])
{
for(int i = 1;i <= n;i++)
{
int q[N], hh = 0, tt = -1;
for(int j = 1;j <= m;j++)
{
while(hh <= tt && cmp(g[i][q[tt]], g[i][j], flag))tt--;
q[++tt] = j;
while(hh <= tt && j - q[hh] >= b)hh++;
res[i][j]=g[i][q[hh]];
}
}
}
void get_c(bool flag,int g[][N], int res[][N])
{
for(int i = 1;i <= m;i++)
{
int q[N], hh = 0, tt = -1;
for(int j = 1;j <= n;j++)
{
while(hh <= tt && cmp(g[q[tt]][i], g[j][i], flag))tt--;
q[++tt] = j;
while(hh <= tt && j - q[hh] >= a)hh++;
res[j][i] = g[q[hh]][i];
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> a >> b;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
cin >> g[i][j];
get_r(false,resmn1);
get_r(true,resmx1);
get_c(false,resmn1,resmn2);
get_c(true,resmx1,resmx2);
ll res = 0;
for(int i = a; i <= n;i++)
for(int j = b;j <= m;j++)
{
res = (res + (ll)(resmn2[i][j] * resmx2[i][j])) % mod;
}
cout << res << endl;
return 0;
}
`feaewsfgaegregsewefawef正解
*************************************
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010,mod = 998244353;
int n,m,a,b,g[N][N],minv1[N][N],maxv1[N][N],minv2[N][N],maxv2[N][N];//maxv1,minv1存放行的值作为中间过渡,minv2,maxv2存放最终的值
//类似于重载比较符号
bool cmp(int a,int b,bool flag)
{
if(flag) return a<=b;//true表示求最大值,所以返回队尾元素小于当前元素
else return a>=b;//false表示求最小值,所以返回队尾元素大于当前元素
}
//flag==true 求最大值 否则求最小值 存放到数组中
void getrows(bool flag,int res[][N])
{
for(int i=1;i<=n;i++)
{
int q[N],hh=0,tt=-1;
for(int j=1;j<=m;j++)
{
while(hh<=tt&&cmp(g[i][q[tt]],g[i][j],flag)) tt--;
q[++tt]=j;
while(j-q[hh]>=b&&hh<=tt) hh++;//太长了出队
res[i][j]=g[i][q[hh]];
}
}
}
//flag==true 求最大值 否则求最小值 存放到数组中
void getcols(bool flag,int g[][N],int res[][N])
{
for(int i=1;i<=m;i++)
{
int q[N],hh=0,tt=-1;
for(int j=1;j<=n;j++)
{
while(hh<=tt&&cmp(g[q[tt]][i],g[j][i],flag)) tt--;
q[++tt]=j;
while(j-q[hh]>=a&&hh<=tt) hh++;//太长了出队
res[j][i]=g[q[hh]][i];
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&g[i][j]);
}
}
//先对行做单调队列求最小值和最大值
getrows(false,minv1);
getrows(true,maxv1);
//再对列做单调队列求最小值和最大值
getcols(false,minv1,minv2);
getcols(true,maxv1,maxv2);
long long res=0;
for(int i=a;i<=n;i++)
{
for(int j=b;j<=m;j++)
{
res=(res+(long long)minv2[i][j]*maxv2[i][j])%mod;
}
}
printf("%lld",res);
return 0;
}