题目描述
给定一个 n×m (n 行 m 列)的矩阵。
设一个矩阵的价值为其所有数中的最大值和最小值的乘积。
求给定矩阵的所有大小为 a×b (a 行 b 列)的子矩阵的价值的和。
答案可能很大,你只需要输出答案对 998244353 取模后的结果。
输入格式
输入的第一行包含四个整数分别表示 n,m,a,b,相邻整数之间使用一个空格分隔。
接下来 n 行每行包含 m 个整数,相邻整数之间使用一个空格分隔,表示矩阵中的每个数 Ai,j。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40% 的评测用例,1≤n,m≤100;
对于 70% 的评测用例,1≤n,m≤500;
对于所有评测用例,1≤a≤n≤1000,1≤b≤m≤1000,1≤Ai,j≤109。
输入样例
2 3 1 2
1 2 3
4 5 6
输入样例
58
(二维单调队列) $O(nm)$
实际上是一个二维单调队列。
有一个长度为b的滑动窗口,在每行从1滑到m,滑动n次
两次滑动窗口内分别维护一个最大值和最小值=====>形成一个n*(m-b+1)的最值矩阵
将每次的滑动窗口视为一个最值元素,维护一个长度为a的滑动窗口,竖着从每列从1滑到n,滑动m-b+1次======>形成一个(n-a+1)*(m-b+1)的滑动矩阵
这里用deque实现,需要加O2优化。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// 实际上是一个二维单调队列,有一个长度为b的滑动窗口,在每行从1滑到m,滑动n次
// 两次滑动窗口内分别维护一个最大值和最小值=====>形成一个n*(m-b+1)的最值矩阵
// 将每次的滑动窗口视为一个最值元素,维护一个长度为a的滑动窗口,竖着从每列从1滑到n,滑动m-b+1次
// ======>形成一个(n-a+1)*(m-b+1)的滑动矩阵
const int N =1010;
int aa[N][N];
int m1[N][N]; //m1[i][j]表示在第i行滑倒第j次的最大值
int m2[N][N]; //m2[i][j]表示在第i行滑倒第j次的最小值
int maxx[N][N];
int minn[N][N];
int nn,mm;
int n,m,a,b;
const int p = 998244353;
void solve_r()
{
int idx = 1;
deque<int> q;
//维护q.front()为最大值(下标)
for(int i=1;i<=m;i++)
{
while(q.size()!=0 && aa[nn][q.back()] < aa[nn][i]) q.pop_back();
q.push_back(i);
while(q.size()!=0 && i-q.front() >= b) q.pop_front();
if(i>=b) m1[nn][idx++] = aa[nn][q.front()];
}
q.clear();
idx = 1;
//min
for(int i=1;i<=m;i++)
{
while(q.size()!=0 && aa[nn][q.back()] > aa[nn][i]) q.pop_back();
q.push_back(i);
while(q.size()!=0 && i-q.front() >= b) q.pop_front();
if(i>=b) m2[nn][idx++] = aa[nn][q.front()];
}
}
void solve_c()
{
int idx = 1;
deque<int> q;
//维护q.front()为最大值(下标)
for(int i=1;i<=n;i++)
{
while(q.size()!= 0 && m1[q.back()][mm] < m1[i][mm]) q.pop_back();
q.push_back(i);
while(q.size()!= 0 && i-q.front() >= a) q.pop_front();
if(i>=a) maxx[idx++][mm] = m1[q.front()][mm];
}
q.clear();
idx = 1;
//min
for(int i=1;i<=n;i++)
{
while(q.size()!= 0 && m2[q.back()][mm] > m2[i][mm]) q.pop_back();
q.push_back(i);
while(q.size()!= 0 && i-q.front() >= a) q.pop_front();
if(i>=a) minn[idx++][mm] = m2[q.front()][mm];
}
}
int main()
{
cin>>n>>m>>a>>b;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cin>>aa[i][j];
}
//每行来一次滑动窗口
for(int i=1;i<=n;i++)
{
nn = i;
solve_r();
}
//每列来一次滑动窗口
for(int i=1;i<=m;i++)
{
mm = i;
solve_c();
}
ll res = 0 ;
for(int i=1;i<=n-a+1;i++)
{
for(int j=1;j<=m-b+1;j++)
res+=(ll)(maxx[i][j]%p)*(minn[i][j]%p)%p;
}
cout<<res<<'\n';
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m-b+1;j++)
cout<<m1[i][j]<<' ';
cout<<'\n';
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m-b+1;j++)
cout<<m2[i][j]<<' ';
cout<<'\n';
}
*/
/*
for(int i=1;i<=n-a+1;i++)
{
for(int j=1;j<=m-b+1;j++)
cout<<maxx[i][j]<<' ';
cout<<'\n';
}
for(int i=1;i<=n-a+1;i++)
{
for(int j=1;j<=m-b+1;j++)
cout<<minn[i][j]<<' ';
cout<<'\n';
}
*/
return 0;
}
O2优化是甚么
给stl的优化