求卡常

#include<bits/stdc++.h>
using namespace std;
const int N=1505;
int n,a[N][N],rt[N*N],idx,ans[2*N],d1[N][N],maidx;
bool vis[20000005];
struct Tree{int ma,ls,rs;}tr[30000005];
void modify(int &u,int l,int r,int x,int d){
	if(!u) u=++idx;
    if(u<=maidx&&!vis[u]) tr[u].ma=tr[u].ls=tr[u].rs=0,vis[u]=1;
	if(l==r){tr[u].ma=max(tr[u].ma,d);return;}
	int mid=(l+r)>>1;
	if(x<=mid) modify(tr[u].ls,l,mid,x,d);
	else modify(tr[u].rs,mid+1,r,x,d);
	tr[u].ma=max(tr[tr[u].ls].ma,tr[tr[u].rs].ma);
}
int query(int &u,int l,int r,int L,int R){
	if(!u) u=++idx;
    if(u<=maidx&&!vis[u]) tr[u].ma=tr[u].ls=tr[u].rs=0,vis[u]=1;
	if(l>=L&&r<=R) return tr[u].ma;
	int mid=(l+r)>>1;
	if(L>mid) return query(tr[u].rs,mid+1,r,L,R);
	if(R<=mid) return query(tr[u].ls,l,mid,L,R);
	int res=0;
	res=max(res,query(tr[u].ls,l,mid,L,R));
	res=max(res,query(tr[u].rs,mid+1,r,L,R));
	return res;
}
int in(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f; 
}
void out(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	n=in();
	//for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=in();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
            a[i][j]=in();
			d1[i][j]=query(rt[a[i][j]],1,n,1,j)+1;
			modify(rt[a[i][j]],1,n,j,d1[i][j]);
		}
	} 
	//memset(tr,0,sizeof(tr));
	//for(int i=1;i<=idx;i++) tr[i].ma=tr[i].ls=tr[i].rs=0;
	for(int i=1;i<=(n*n);i++) rt[i]=0;
	maidx=idx;idx=0;
	for(int i=n;i>=1;i--){
		for(int j=n;j>=1;j--){
            int res;
			res=query(rt[a[i][j]],1,n,j,n)+1;
			modify(rt[a[i][j]],1,n,j,res);
            ans[d1[i][j]+res-1]++;
		}
	}
	for(int i=1;i<=(2*n-1);i++) out(ans[i]),putchar('\n');
}