Description
给定一个n行m列的矩阵，请对于每个长宽均为k的连续子正方形，统计里面出现过的数值的种类数。
Input
第一行包含三个正整数n,m,k(n,m<=3000,k<=min(n,m))。
接下来n行，每行m个正整数a[i][j](1<=a[i][j]<=100000)，表示矩阵中每个位置的数值。
Output
输出一行两个整数M和S。
设f(i,j)表示以(i,j)为左上角的正方形内出现过的数值的种类数，则M表示f的最大值，S表示f的总和。
对每种颜色分别算贡献，一个点对一个边长k的正方形内每个位置贡献1，但同色贡献只算一次，这是一个正方形求并问题。考虑扫描线，由于边长固定，每个正方形进入和离开扫描线时，至多改变扫描线一个区间的状态，求这个区间的端点，则需要在扫描线上查前趋后继，可以用线段树维护。
#include<bits/stdc++.h>
typedef unsigned int u32;
const u32 A=-;
const int N=1e5+,M=;
char ib[M*M*],*ip=ib;
inline int _(){
int x=;
while(*ip<)++ip;
while(*ip>)x=x*+*ip++-;
return x;
}
u32 bs[M][][M/+],t0[N][],t1[N][M/+];
int n,m,k,mx,a[M][M],s[M][M],pv[N];
long long sum;
inline void _xor(u32*a,int x){a[x>>]^=<<x;}
inline int _get(u32*a,int x){return a[x>>]>>x&;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
#define ctz(x) __builtin_ctz(x)
#define clz(x) (31^__builtin_clz(x))
inline void cal(int x,int y,int w,int sgn){
int L=-,R=,p1=y>>,p2=y>>,p3;
u32 v;
v=t1[w][p1]&A<<y;
if(v)R=p1<<|ctz(v);
else{
v=t0[w][p2]&A<<p1<<;
if(v){
p3=p2<<|ctz(v);
R=p3<<|ctz(t1[w][p3]);
}else for(int i=p2+;i<;++i)if(t0[w][i]){
p3=i<<|ctz(t0[w][i]);
R=p3<<|ctz(t1[w][p3]);
break;
}
}
v=t1[w][p1]&A>>(^y);
if(v)L=p1<<|clz(v);
else{
v=t0[w][p2]&A>>(^p1)>>;
if(v){
p3=p2<<|clz(v);
L=p3<<|clz(t1[w][p3]);
}else for(int i=p2-;i>=;--i)if(t0[w][i]){
p3=i<<|clz(t0[w][i]);
L=p3<<|clz(t1[w][p3]);
break;
}
} L=max(y,L+k);
R=min(min(m+,y+k),R);
if(L<R)s[x][L]+=sgn,s[x][R]-=sgn;
}
inline void del(int x,int y,int w){
_xor(t1[w],y);
if(!t1[w][y>>])_xor(t0[w],y>>);
cal(x,y,w,-);
}
inline void ins(int x,int y,int w){
cal(x,y,w,);
if(!t1[w][y>>])_xor(t0[w],y>>);
_xor(t1[w],y);
}
int main(){
fread(ib,,sizeof(ib),stdin);
n=_();m=_();k=_();
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
a[i][j]=_();
}
}
for(int j=;j<=m;++j){
for(int i=;i<=n;++i){
int x=a[i][j],&y=pv[x];
if(y&&y>i-k)_xor(bs[y][],j),_xor(bs[i][],j);
y=i;
}
for(int i=;i<=n;++i)pv[a[i][j]]=;
}
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
if(i>k&&!_get(bs[i-k][],j))del(i,j,a[i-k][j]);
if(!_get(bs[i][],j))ins(i,j,a[i][j]);
}
}
for(int i=;i<=n;++i){
for(int j=;j<=m;++j)s[i][j]+=s[i][j-];
for(int j=;j<=m;++j)s[i][j]+=s[i-][j];
if(i>=k)for(int j=k;j<=m;++j){
sum+=s[i][j];
if(s[i][j]>mx)mx=s[i][j];
}
}
printf("%d %lld\n",mx,sum);
return ;
}