CodeForces 15D Map

洛谷题目页面传送门 & codeforces题目页面传送门

题意见洛谷里的翻译。（注意翻译里有错误，应该是优先选上面的矩阵，在同一行的优先选左边的矩阵）

这题一看就会做啊

（以下设大矩阵是\(n\times m\)，小矩阵是\(n0\times m0\)，第\(i\)行第\(j\)列高度为\(a_{i,j}\)）

不难想到可以预处理出二位前缀和数组\(sum\)，后面就可以\(\mathrm{o}(1)\)求出一个小矩阵的和；然后跑\(2\)遍单调队列，第\(1\)次求出\(\forall i\in[1,n],\forall j\in[1,m-m0+1],mn1_{i,j}=\min\limits_{k=j}^{j+m0-1}\{a_{i,k}\}\)，第二次求出\(\forall i\in[1,n-n0+1],\forall j\in[1,m-m0+1],mn2_{i,j}=\min\limits_{k=i}^{k+n0-1}\{\min\limits_{o=j}^{j+m0-1}\{a_{k,o}\}\}=\min\limits_{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\times m0\times 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()<<"\n";//输出选的小矩阵的个数 
    for(ri i=0;i<ans.size();i++)printf("%lld %lld %lld\n",ans[i].x,ans[i].y,cst[ans[i].x][ans[i].y]);//输出选的小矩阵 
    return 0;
}