用凡科做的网站保存不了,不要钱做网站软件,Myeclipse怎么做网站,儿童摄影网站建设蓝桥集训之子矩阵 核心思想#xff1a;二维单调队列 先求每一行中列长为B的区间的最值再在最值数组中求行长为A的区间的最值 – 区间最值最后遍历所有最大最小值相乘的结果 #include iostream#include cstring#include algorithmusing namespa…蓝桥集训之子矩阵 核心思想二维单调队列 先求每一行中列长为B的区间的最值再在最值数组中求行长为A的区间的最值 – 区间最值最后遍历所有最大最小值相乘的结果 #include iostream#include cstring#include algorithmusing namespace std;const int N 1010,MOD 998244353;typedef long long LL;int w[N][N];int n,m,A,B;int row_max[N][N],row_min[N][N];int q[N];void getmax(int a[],int b[],int tot,int k) //a数组共tot个数中找长度为k的区间最值放入b{int hh0,tt-1;for(int i0;itot;i){if(hhtt q[hh] i-k1) hh;while(hhtt a[q[tt]] a[i]) tt--;q[tt] i;b[i] a[q[hh]];}}void getmin(int a[],int b[],int tot,int k) //a数组共tot个数中找长度为k的区间最值放入b{int hh0,tt-1;for(int i0;itot;i){if(hhtt q[hh] i-k1) hh;while(hhtt a[q[tt]] a[i]) tt--;q[tt] i;b[i] a[q[hh]];}}int main(){ios::sync_with_stdio(false);cin.tie(0);cinnmAB;for(int i0;in;i)for(int j0;jm;j)cinw[i][j];for(int i0;in;i){getmax(w[i],row_max[i],m,B); //列长B的区间最值getmin(w[i],row_min[i],m,B);}int ans0;int a[N],b[N],c[N];for(int iB-1;im;i){for(int j0;jn;j) a[j] row_max[j][i]; //取出第j列的所有最值getmax(a,b,n,A); //将区间最大值存入bfor(int j0;jn;j) a[j] row_min[j][i];getmin(a,c,n,A); //将区间最小值存入cfor(int jA-1;jn;j)ans (ans (LL) b[j] * c[j] ) %MOD;}coutansendl;return 0;}
