思路
单调队列板子。
设 \(b_{i,j}\) 表示第 \(i\) 行，区间为 \(j\) 到 \(j+y-1\) 的最小值，不难发现这个可以用单调队列 \(O(nm)\) 预处理出来。
接下来我们的问题就转化成了有一个矩阵，求所有宽为 \(1\)，长为 \(x\) 的子矩阵的最小值之和。
这个问题也十分好做，直接枚举列，然后在每一行单调队列即可。
代码
/*
A tree without skin will surely die.
A man without face is invincible.
*/
#include<bits/stdc++.h>
using namespace std;
int const N=3e3+10;
int ans,n,m,a[N][N],b[N][N],g[N*N];
struct node{int w,id;}q[N];
inline void go(int x,int y){
for (int i=1;i<=n;++i){
int l=1,r=0;
for (int j=1;j<=y;++j){
while (l<=r && q[r].w>=a[i][j]) --r;
q[++r].w=a[i][j];q[r].id=j;
}
b[i][1]=q[l].w;
for (int j=y+1;j<=m;++j){
while (q[l].id<=j-y && l<=r) ++l;
while (l<=r && q[r].w>=a[i][j]) --r;
q[++r].w=a[i][j];q[r].id=j;
b[i][j-y+1]=q[l].w;
}
}
for (int j=1;j<=m-y+1;++j){
int l=1,r=0;
for (int i=1;i<=x;++i){
while (l<=r && q[r].w>=b[i][j]) --r;
q[++r].w=b[i][j];q[r].id=i;
}
ans+=q[l].w;
for (int i=x+1;i<=n;++i){
while (q[l].id<=i-x && l<=r) ++l;
while (l<=r && q[r].w>=b[i][j]) --r;
q[++r].w=b[i][j];q[r].id=i;ans+=q[l].w;
}
}
}
signed main(){
//读入
for (int i=1;i<=n*m;++i) g[i]=(g[i-1]*xx%zz+yy)%zz;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j) a[i][j]=g[(i-1)*m+j-1];
go(x,y);//输出
return 0;
}