题解

我和“ACGO之星”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1695017759936430080

#include<bits/stdc++.h>
#define ll long long
#define ffd(x) memset(x,0,sizeof(x))
using namespace std;
int a,b,n,m,xmin[1004][1004],cnt,ymin[1004][1004],hmin,tmin,dlmin[1004];
ll ans[1000003][3],aa[1004][1004];
struct sum{
	ll sum[1222][1222];
	void init(int n,int m){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=m;j++){
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+aa[i][j];
			}
		}
	}
	inline ll query(int nn,int mm,int n,int m){
		return sum[n][m]-sum[nn-1][m]-sum[n][mm-1]+sum[nn-1][mm-1];
	}
}S;
inline void check(int pos){
    while (hmin<=tmin&&dlmin[hmin]<=pos) hmin++;
}
inline void addmin(int z,int xx){
    while (hmin<=tmin&&aa[z][dlmin[tmin]]>aa[z][xx]) tmin--;
    dlmin[++tmin]=xx;
}
inline ll read(){
    ll x=0;char ch=getchar();ll f=1;
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
priority_queue<pair<ll,pair<ll,ll> > > dl;
//实现采用优先队列+pair，主要是因为比较懒
//我们要小根堆，所以我把里面所有的数都存了负值
bool vis[1201][1201];
int main(){
    scanf("%d%d%d%d",&n,&m,&a,&b);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            aa[i][j]=read();
        }
    }
    for (int i=1;i<=n
    ;i++){
        hmin=1;tmin=0;ffd(dlmin);
        for (int j=1;j<=m;j++){
            addmin(i,j);
            if (j>=b){
                check(j-b);
                xmin[i][j-b+1]=aa[i][dlmin[hmin]];
            }
        }
    }
    for (int j=1;j<=m-b+1;j++){
        hmin=1;tmin=0;ffd(dlmin);
        for (int i=1;i<=n;i++){
            while (hmin<=tmin&&xmin[dlmin[tmin]][j]>xmin[i][j]) tmin--;
            dlmin[++tmin]=i;
            if (i>=a){
                while (hmin<=tmin&&dlmin[hmin]<=i-a) hmin++;
                ymin[i-a+1][j]=xmin[dlmin[hmin]][j];
            }
        }
    }//前面全都是单调队列求最小值，不会的可以点上个链接
    S.init(n,m);
    for (int i=1;i<=n-a+1;i++){
    	for (int j=1;j<=m-b+1;j++){
    		//cout<<(S.query(i,j,i+a-1,j+b-1)-1LL*a*b*ymin[i][j])<<" "<<i<<" "<<j<<endl;
    		dl.push(make_pair(-(S.query(i,j,i+a-1,j+b-1)-1LL*a*b*ymin[i][j]),make_pair(-i,-j)));
//我们要小根堆，所以我把里面所有的数都存了负值
		}
	}
	while (!dl.empty()){
		ll ANS=-dl.top().first,posx=-dl.top().second.first,posy=-dl.top().second.second;
		dl.pop();
		if (vis[posx][posy]) continue;
		ans[++cnt][0]=ANS,ans[cnt][1]=posx,ans[cnt][2]=posy;
		for (int i=max(1LL,posx-a+1);i<=posx+a-1;i++){
			for (int j=max(1LL,posy-b+1);j<=posy+b-1;j++){
				vis[i][j]=1;//打标记
			}	
		}
	}
	printf("%d\n",cnt);
	for (int i=1;i<=cnt;i++){
		printf("%lld %lld %lld\n",ans[i][1],ans[i][2],ans[i][0]);
	}
}