思路就是暴力转移优化。

#include<bits/stdc++.h>
//#define int long long  
#define Maxn 1505 
using namespace std;
struct node {
	int x,y;
} vis[Maxn*Maxn];
int a[Maxn][Maxn];
bool pera(node x,node y,node s)
{return max(abs(s.x-x.x),abs(s.y-x.y)) > max(abs(s.x-x.x),abs(s.y-x.y));}
struct node1 {
	int len;
	node o;
	bool operator<(const node1&is)
	const {return len < is.len;}
};
priority_queue<node1> Q[Maxn][Maxn];
int get(node x,node s) {
	return max(abs(s.x-x.x),abs(s.y-x.y))+1;
}
int n,q;
void solvelen(int x,int y) {
	vector<node1> p;
	int lst = min((n-x+1),(n-y+1))+1;
	while(!Q[x][y].empty()&&((int)Q[x][y].size() > q||Q[x][y].top().len >= lst))
		p.push_back(Q[x][y].top()),lst = min(lst,Q[x][y].top().len),Q[x][y].pop();
	while(!p.empty()&&p.back().len == lst)Q[x][y].push(p.back()),p.pop_back();
}
void dofor(int x,int y,int v,int w) {
//	cout<<x<<" "<<y<<" "<<v<<" "<<w<<"+++\n";
	queue<int> p;
	vis[a[x][y]] = {x,y};
	p.push(a[x][y]);
	queue<node1> O;
	while(!Q[x+v][y+w].empty()) {
		auto u = Q[x+v][y+w].top().o;
		O.push(Q[x+v][y+w].top()); 
		Q[x+v][y+w].pop();
		if(!vis[a[u.x][u.y]].x)
			vis[a[u.x][u.y]] = u,
			p.push(a[u.x][u.y]);
		else if(pera(vis[a[u.x][u.y]],u,{x,y}))
			vis[a[u.x][u.y]] = u;
	}
	while(!p.empty()) {
		Q[x][y].push({get(vis[p.front()],{x,y}),vis[p.front()]});
//		cout<<p.front()<<" "<<vis[p.front()].x<<" "<<vis[p.front()].y<<" "<<get(vis[p.front()],{x,y})<<"\n";
		vis[p.front()] = {0,0};
		p.pop();
	}
	while(!O.empty())Q[x+v][y+w].push(O.front()),O.pop();
	solvelen(x,y);
}
void dofor__(int x,int y) {
//	cout<<x<<" "<<y<<" "<<"+++\n";
	queue<int> p;
	vis[a[x][y]] = {x,y};
	p.push(a[x][y]);
	queue<node1> O;
	while(!Q[x+1][y].empty()) {
		auto u = Q[x+1][y].top().o;
		O.push(Q[x+1][y].top()); 
		Q[x+1][y].pop();
		if(!vis[a[u.x][u.y]].x)
			vis[a[u.x][u.y]] = u,
			p.push(a[u.x][u.y]);
//			cout<<u.x<<" "<<u.y<<"\n";
		else if(max(vis[a[u.x][u.y]].x-x,vis[a[u.x][u.y]].y-y)+1 > max(u.x-x,u.y-y)+1)
			vis[a[u.x][u.y]] = u;
//			cout<<u.x<<" "<<u.y<<"\n";
	}
//	cout<<"******\n";
	while(!O.empty())Q[x+1][y].push(O.front()),O.pop();
	while(!Q[x][y+1].empty()) {
		auto u = Q[x][y+1].top().o;
		O.push(Q[x][y+1].top()); 
		Q[x][y+1].pop();
		if(!vis[a[u.x][u.y]].x)
			vis[a[u.x][u.y]] = u,
			p.push(a[u.x][u.y]);
//			cout<<u.x<<" "<<u.y<<"\n";
		else {
			if(max(vis[a[u.x][u.y]].x-x,vis[a[u.x][u.y]].y-y)+1 > max(u.x-x,u.y-y)+1)
//			cout<<u.x<<" "<<u.y<<"\n",
			vis[a[u.x][u.y]] = u;
		}
	}
	while(!O.empty())Q[x][y+1].push(O.front()),O.pop();
	while(!p.empty()) {
		Q[x][y].push({get(vis[p.front()],{x,y}),vis[p.front()]});
//		cout<<p.front()<<" "<<vis[p.front()].x<<" "<<vis[p.front()].y<<" "<<get(vis[p.front()],{x,y})<<"\n";
		vis[p.front()] = {0,0};
		p.pop();
	}
	solvelen(x,y);
}
int tr[Maxn];
void add(int x,int val) {
	for(;x<Maxn;x+=x&-x)
		tr[x] += val;
}
int ask(int x) {
	int ans = 0;
	for(;x>0;x-=x&-x)
		ans += tr[x];
	return ans;
}
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	for(auto &u:vis)u = {0,0};
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	Q[n][n].push({1,{n,n}});
	for(int x=n-1;x>=1;x--)
		dofor(x,n,1,0);
	for(int y=n-1;y>=1;y--)
		dofor(n,y,0,1);
	for(int x=n-1;x>=1;x--)
		for(int y=n-1;y>=1;y--)
			dofor__(x,y);
	for(int i=1;i<=n;i++) {
//		cout<<i<<"===\n";
		for(int j=1;j<=n;j++) {
//			cout<<j<<"---\n";
//			while(!Q[i][j].empty())cout<<Q[i][j].top().o.x<<" "<<Q[i][j].top().o.y<<" "<<Q[i][j].top().len<<"\n",Q[i][j].pop();
			int len;
			if((int)Q[i][j].size() <= q)
				len = min(n-i+1,n-j+1);
			else len = min(min(n-i+1,n-j+1),Q[i][j].top().len-1);
			add(1,1); add(len+1,-1);
//			cout<<len<<" ";
//			cout<<"---\n";
		}
//		cout<<"===\n";
//		cout<<"\n";
	}
	for(int i=1;i<=n;i++)
		cout<<ask(i)<<"\n";
	return 0;
 }