编程一小时2023.5.19

发布时间 2023-05-20 22:47:34作者: Verneyyx

#include<iostream>
#include<cstring>
using namespace std;
const int N=1010,mod=998244353;
int g[N][N],min1[N][N],min2[N][N],max1[N][N],max2[N][N];
int n,m,a,b;

void getmin1(int id){
int q[N],tt=-1,hh=0;
for(int i=1;i<=m;i++){
while(tt>=hh&&i-q[hh]+1>b)hh++;
while(tt>=hh&&g[id][q[tt]]>=g[id][i])tt--;
q[++tt]=i;
if(i>=b)min1[id][i]=g[id][q[hh]];

}
}

void getmin2(int id){
int q[N],tt=-1,hh=0;
for(int i=1;i<=n;i++){
while(tt>=hh&&i-q[hh]+1>a)hh++;
while(tt>=hh&&min1[q[tt]][id]>=min1[i][id])tt--;
q[++tt]=i;
if(i>=a)min2[i][id]=min1[q[hh]][id];

}
}

void getmax1(int id){
int q[N],tt=-1,hh=0;
for(int i=1;i<=m;i++){
while(tt>=hh&&i-q[hh]+1>b)hh++;
while(tt>=hh&&g[id][q[tt]]<=g[id][i])tt--;
q[++tt]=i;
if(i>=b)max1[id][i]=g[id][q[hh]];

}
}

void getmax2(int id){
int q[N],tt=-1,hh=0;
for(int i=1;i<=n;i++){
while(tt>=hh&&i-q[hh]+1>a)hh++;
while(tt>=hh&&max1[q[tt]][id]<=max1[i][id])tt--;
q[++tt]=i;
if(i>=a)max2[i][id]=max1[q[hh]][id];

}
}


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]);

for(int i=1;i<=n;i++) getmin1(i);
for(int i=b;i<=m;i++)getmin2(i);
for(int i=1;i<=n;i++)getmax1(i);
for(int i=b;i<=m;i++)getmax2(i);

long long res(0);

for(int i=a;i<=n;i++)
for(int j=b;j<=m;j++) res+=((long long)min2[i][j]*max2[i][j])%mod,res%=mod;

printf("%d\n",res);
return 0;
}