AcWing 4964. 子矩阵--二维单调队列--一维求二次
原题链接
中等
作者:
CqAq
,
2024-04-06 16:31:54
,
所有人可见
,
阅读 9
算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define inf 998244353
const int N = 1E3 + 5;
ll n, m, a, b;
ll mp[N][N], mxans[N][N], mians[N][N], q[N];//单调队列
ll mxline[N][N], miline[N][N];
//二维单调队列
void linemx(){
//int tag = 1;
for(int i = 1; i <= n; ++ i){
int hh = 1, tt = 0;
for(int j = 1; j <= m; ++ j){
while(hh <= tt && q[hh] < j - b + 1) ++ hh;
while(hh <= tt && mp[i][q[tt]] <= mp[i][j]) -- tt;
q[++ tt] = j;
if(j - b + 1 >= 1) mxline[i][j - b + 1] = mp[i][q[hh]];
}
}
}
void linemxans(){ //纵向求最大应该是以横向求完的数组为基准
// memset(mx, 0, sizeof(mx));
int tag = 1;
for(int j = 1; j <= m; ++ j){
int hh = 1, tt = 0;
for(int i = 1; i <= n; ++ i){
while(hh <= tt && q[hh] < i - a + 1) ++ hh;
while(hh <= tt && mxline[q[tt]][j] < mxline[i][j]) -- tt;
q[++ tt] = i;
if(i - a + 1 >= 1) mxans[i - a + 1][j] = mxline[q[hh]][j];
}
}
}
void linemi(){
int tag = 1;
for(int i = 1; i <= n; ++ i){
int hh = 1, tt = 0;
for(int j = 1; j <= m; ++ j){
while(hh <= tt and q[hh] < j - b + 1) ++ hh;
while(hh <= tt && mp[i][q[tt]] > mp[i][j]) -- tt;
q[++ tt] = j;
if(j - b + 1 >= 1) miline[i][j - b + 1] = mp[i][q[hh]];
}
}
}
void linemians(){ //纵向求最大应该是以横向求完的数组为基准
// memset(mi, 0, sizeof(mi));
int tag = 1;
for(int j = 1; j <= m; ++ j){
int hh = 1, tt = 0;
for(int i = 1; i <= n; ++ i){
while(hh <= tt && q[hh] < i - a + 1) ++ hh;
while(hh <= tt && miline[q[tt]][j] >= miline[i][j]) -- tt;
q[++ tt] = i;
if(i - a + 1 >= 1) mians[i - a + 1][j] = miline[q[hh]][j];
}
}
}
void solve(){
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j) cin >> mp[i][j];
linemx();
linemxans();
linemi();
linemians();
ll res = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
res = (res + mians[i][j] * mxans[i][j] % inf) % inf;
cout << res << '\n';
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> a >> b;
solve();
return 0;
}