这题思路就是用两次单调队列。
下面是TIE的代码。9/10；用了priority_queue做单调队列，而不是手动写的。
（手写单调队列好麻烦~~~，脑子晕死，考试的时候过了9个点也ok，）
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 1E3+10;
const int mod = 998244353;
typedef long long ll;
typedef pair<int,int> pll;
priority_queue<pll> maxn[N];
priority_queue<pll,vector<pll>,greater<pll>> minn[N];
int maxnum[N][N];
int minnum[N][N];
priority_queue<pll> maxl[N];
priority_queue<pll,vector<pll>,greater<pll>> minl[N];
int main (){
int n,m,a,b;cin>>n>>m>>a>>b;
for(int i = 1;i<=n;++i){
for(int j = 1;j<=m;++j){
int a;cin>>a;
maxn[i].push({a,j});
minn[i].push({a,j});
while(maxn[i].top().second<=j-b){
maxn[i].pop();
}
while(minn[i].top().second<=j-b){
minn[i].pop();
}
maxnum[i][j] = maxn[i].top().first;
minnum[i][j] = minn[i].top().first;
}
}
ll hou = 0;
ll ou = 0;
for(int j = b;j<=m;++j){
for(int i = 1;i<=n;++i){
maxl[j].push({maxnum[i][j],i});
minl[j].push({minnum[i][j],i});
if(i>=a){
while(maxl[j].top().second<=i-a){
maxl[j].pop();
}
while(minl[j].top().second<=i-a){
minl[j].pop();
}
hou = (ll)maxl[j].top().first*(ll)minl[j].top().first%mod;
ou = (ou+hou)%mod;
cout<<hou<<endl;
}
}
}
cout<<ou;
return 0;
} 单调队列
