洛谷题目页面传送门 & CodeForces题目页面传送门
题意见洛谷里的翻译。（注意翻译里有错误，应该是优先选上面的矩阵，在同一行的优先选左边的矩阵）
这题一看就会做啊
（以下设大矩阵是(n imes m)，小矩阵是(n0 imes m0)，第(i)行第(j)列高度为(a_{i,j})）
不难想到可以预处理出二维前缀和数组(Sum)，后面就可以(mathrm{O}(1))求出一个小矩阵的和；然后跑(2)遍单调队列，第(1)次求出(forall iin[1,n],forall jin[1,m-m0+1],mn1_{i,j}=minlimits_{k=j}^{j+m0-1}{a_{i,k}})，第二次求出(forall iin[1,n-n0+1],forall jin[1,m-m0+1],mn2_{i,j}=minlimits_{k=i}^{k+n0-1}left{minlimits_{o=j}^{j+m0-1}{a_{k,o}}
ight}=minlimits_{k=i}^{k+n0-1}{mn1_{k,j}})。那么一个左上角在((i,j))的小矩阵的花费显然是(Sum_{i+n0-1,j+m0-1}-Sum_{i-1,j+m0-1}-Sum_{i+n0-1,j-1}+Sum_{i-1,j-1}-n0 imes m0 imes mn2_{i,j})了。然后把所有小矩阵排个序，从头到尾扫一遍，如果一个小矩阵中有已经被标记的格子了，就不选；否则就选，并且把它所覆盖的格子都标记一下。但这样会TLE。不难想到，判一个小矩阵有没有被标记过的格子，只需要判四个角就可以了，这样判的时间总共就是(mathrm{O}(nm))了；而每个格子最多会被标记一次，所以标记总共也是(mathrm{O}(nm))，这样就不会TLE了。（或者你用树状数组、线段树或其他一些更高级的数据结构我也不拦你）
对了，这题非常的卡常。我第一次交，T了。然后加了个快读，还是T了。然后把所有int改成register int，还是T了。最后我发现，原来计算一个小矩阵的花费虽然(mathrm{O}(1))，但是常数略大，而我却把它放在sort的cmp里计算，等于在扩大计算花费的常数（众所周知，快排里一个元素可能和多个元素比较）。于是我事先计算所有小矩阵的花费，然后存下来，cmp的时候直接调用，然后就AC了。
下面贴上蒟蒻又长又丑的代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define ri register int//呵呵
void read(int &x){//快读
x=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
const int N=1000,M=1000;
int n,m/*大矩阵的尺寸*/,n0,m0/*小矩阵的尺寸*/;
int a[N+1][M+1];//高度
int Sum[N+1][M+1];//二维前缀和
int q[N],head,tail;//单调队列
int mn1[N+1][M+1]/*一维最小值*/,mn2[N+1][M+1]/*二维最小值*/;
vector<pair<int,int> > ord;//小矩阵访问顺序
int cst[N+1][M+1];//小矩阵的花费
int calc_cst(int x,int y){//计算左上角在(x,y)的小矩阵的花费
return Sum[x+n0-1][y+m0-1]-Sum[x-1][y+m0-1]-Sum[x+n0-1][y-1]+Sum[x-1][y-1]-n0*m0*mn2[x][y];
}
bool cmp(pair<int,int> x,pair<int,int> y){//排序方式，以花费为第一关键字从小到大、行数为第二关键字从小到大、列数为第三关键字从小到大排序
return cst[x.X][x.Y]!=cst[y.X][y.Y]?cst[x.X][x.Y]<cst[y.X][y.Y]:x.X!=y.X?x.X<y.X:x.Y<y.Y;
}
bool vis[N+1][M+1];//标记
signed main(){
// freopen("C:\Users\chenx\OneDrive\桌面\data.in","r",stdin);
read(n);read(m);read(n0);read(m0);
for(ri i=1;i<=n;i++)for(ri j=1;j<=m;j++){
read(a[i][j]);
Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+a[i][j];//预处理二维前缀和
}
for(ri i=1;i<=n;i++){//第一次单调队列，算mn1
head=tail=0;
for(ri j=1;j<m0;j++){
while(head<tail&&a[i][q[tail-1]]>=a[i][j])tail--;
q[tail++]=j;
}
for(ri j=1;j+m0-1<=m;j++){
while(head<tail&&q[head]<j)head++;
while(head<tail&&a[i][q[tail-1]]>=a[i][j+m0-1])tail--;
q[tail++]=j+m0-1;
mn1[i][j]=a[i][q[head]];
}
}
// for(ri i=1;i<=n;i++){for(ri j=1;j+m0-1<=m;j++)cout<<mn1[i][j]<<" ";puts("");}puts("");
for(ri j=1;j+m0-1<=m;j++){//第二次单调队列，算mn2
head=tail=0;
for(ri i=1;i<n0;i++){
while(head<tail&&mn1[q[tail-1]][j]>=mn1[i][j])tail--;
q[tail++]=i;
}
for(ri i=1;i+n0-1<=n;i++){
while(head<tail&&q[head]<i)head++;
while(head<tail&&mn1[q[tail-1]][j]>=mn1[i+n0-1][j])tail--;
q[tail++]=i+n0-1;
mn2[i][j]=mn1[q[head]][j];
}
}
// for(ri i=1;i+n0-1<=n;i++){for(ri j=1;j+m0-1<=m;j++)cout<<mn2[i][j]<<" ";puts("");}
for(ri i=1;i+n0-1<=n;i++)for(ri j=1;j+m0-1<=m;j++)cst[i][j]=calc_cst(i,j)/*存花费*/,ord.pb(mp(i,j));
sort(ord.begin(),ord.end(),cmp);//排序
vector<pair<int,int> > ans;//答案序列
for(ri i=0;i<ord.size();i++){
int x=ord[i].X,y=ord[i].Y;
if(vis[x][y]||vis[x][y+m0-1]||vis[x+n0-1][y]||vis[x+n0-1][y+m0-1])continue;//判四个角
ans.pb(ord[i]);//放到答案序列里
for(ri j=x;j<=x+n0-1;j++)for(ri k=y;k<=y+m0-1;k++)vis[j][k]=true;//标记
}
cout<<ans.size()<<"
";//输出选的小矩阵的个数
for(ri i=0;i<ans.size();i++)printf("%lld %lld %lld
",ans[i].X,ans[i].Y,cst[ans[i].X][ans[i].Y]);//输出选的小矩阵
return 0;
}