神仙扫描线题？遵从 JZOJ 题解中的说法写了个 bitset 后来发现可以用线段树。
（JZOJ 上的只能 bitset，空间卡得紧）
维护一个宽度为 \(k\) 的扫描线，并维护其上的 \(m - k + 1\) 个正方形。
每次只会新增一行减少一行的贡献。
由于边长是确定的，所以新增 / 减少某个位置的贡献一定是第二维的某个区间。
对于每种颜色用 bitset 维护其出现的列，则只要能求得该位置的前驱后继即可得到该区间。
于是差分 + 前缀和即可。
（话说 JZOJ 上卡得有点紧，于是特判掉了搬题人的一个 subtask
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
using namespace std;
const int N = 3e3;
const int A = 1e5;
int n,m,k,a[N + 5][N + 5],mx;
int sum[N + 5][N + 5];
int las[A + 5],g[N + 5][N + 5],c[N + 5];
int f[N + 5];
int cur,cnt[A + 5];
bitset<N + 5> vis0[A + 5],vis1[A + 5];
int ans0;
long long ans1;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
scanf("%d",a[i] + j),mx = max(mx,a[i][j]);
if(mx <= 2)
{
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (a[i][j] == 2);
for(register int i = 1,cur;i + k - 1 <= n;++i)
for(register int j = 1;j + k - 1 <= m;++j)
cur = (bool)(sum[i + k - 1][j + k - 1] - sum[i - 1][j + k - 1] - sum[i + k - 1][j - 1] + sum[i - 1][j - 1]) + (bool)(k * k - (sum[i + k - 1][j + k - 1] - sum[i - 1][j + k - 1] - sum[i + k - 1][j - 1] + sum[i - 1][j - 1])),
ans0 = max(ans0,cur),ans1 += cur;
printf("%d %lld\n",ans0,ans1);
return 0;
}
for(register int i = 1;i <= A;++i)
las[i] = n + 1;
for(register int j = 1;j <= m;++j)
{
for(register int i = n;i;--i)
g[i][j] = las[a[i][j]] <= min(i + k,n),las[a[i][j]] = i;
for(register int i = 1;i <= n;++i)
las[a[i][j]] = n + 1;
}
for(register int i = 1;i <= A;++i)
vis0[i][m + 1] = vis1[i][m + 1] = 1;
for(register int i = 1;i <= k;++i)
for(register int j = 1;j <= m;++j)
vis0[a[i][j]][m - j + 1] = 1,vis1[a[i][j]][j] = 1;
for(register int i = 1;i <= k;++i)
for(register int j = 1;j <= k;++j)
cur += !cnt[a[i][j]]++;
f[1] = cur,ans0 = max(ans0,cur),ans1 += cur;
for(register int i = 2;i + k - 1 <= m;++i)
{
for(register int j = 1;j <= k;++j)
cur -= !--cnt[a[j][i - 1]],cur += !cnt[a[j][i + k - 1]]++;
f[i] = cur,ans0 = max(ans0,cur),ans1 += cur;
}
for(register int i = 2;i + k - 1 <= n;++i)
{
memset(c,0,sizeof c);
for(register int j = 1,prev,succ;j <= m;++j)
if(!vis1[a[i + k - 1][j]][j])
{
prev = m - vis0[a[i + k - 1][j]]._Find_next(m - j + 1) + 1;
succ = vis1[a[i + k - 1][j]]._Find_next(j);
vis0[a[i + k - 1][j]][m - j + 1] = 1,vis1[a[i + k - 1][j]][j] = 1;
if(prev + k <= succ)
++c[max(max(prev + 1,j - k + 1),1)],--c[min(min(succ - k + 1,j + 1),m + 1)];
}
for(register int j = 1;j + k - 1 <= m;++j)
c[j] += c[j - 1],f[j] += c[j];
memset(c,0,sizeof c);
for(register int j = 1,prev,succ;j <= m;++j)
if(!g[i - 1][j])
{
prev = m - vis0[a[i - 1][j]]._Find_next(m - j + 1) + 1;
succ = vis1[a[i - 1][j]]._Find_next(j);
vis0[a[i - 1][j]][m - j + 1] = 0,vis1[a[i - 1][j]][j] = 0;
if(prev + k <= succ)
--c[max(max(prev + 1,j - k + 1),1)],++c[min(min(succ - k + 1,j + 1),m + 1)];
}
for(register int j = 1;j + k - 1 <= m;++j)
c[j] += c[j - 1],f[j] += c[j],ans0 = max(ans0,f[j]),ans1 += f[j];
}
printf("%d %lld\n",ans0,ans1);
}