题目理解

我们有一个 $m \times n$ 的矩阵 $A$，要计算所有 $k \times k$ 子矩阵（称为 $k$-片段）的“多样性”，即子矩阵中不同数字的个数。

要求输出：

1. 所有 $k$-片段中最大的多样性值
2. 所有 $k$-片段多样性值的总和

---

暴力方法分析

直接枚举所有 $k$-片段，对每个片段用哈希表统计不同元素个数：

• 子矩阵数量：$(m-k+1) \times (n-k+1)$
• 每个子矩阵大小：$k^2$
• 总复杂度：$O(mn k^2)$

当 $m,n,k \le 3000$ 时，$mnk^2$ 会达到 $10^{13}$ 级别，显然不可行。

---

高效算法思路

我们需要一种方法，在滑动子矩阵时，快速更新不同元素的个数。

核心思想：二维滑动窗口 + 计数数组

1. 二维滑动窗口
   先按行滑动，再按列滑动，维护当前 $k \times k$ 窗口内每个数值的出现次数。

2. 维护“不同元素个数”
   用一个计数数组 cnt[x] 记录当前窗口中数值 $x$ 的出现次数，一个变量 distinct 记录当前不同元素个数。

3. 滑动更新

   • 当某个数值的计数从 0 变 1：distinct++
   • 当某个数值的计数从 1 变 0：distinct--

---

算法步骤

步骤 1：按列预处理

对于每一列 $j$，我们先用一个长度为 $m$ 的滑动窗口（高度 $k$）计算每个行区间 $[i, i+k-1]$ 内该列的元素情况。

具体来说，我们可以先对每一列做一次垂直方向的滑动窗口，记录每个 $k \times 1$ 竖条的信息。

步骤 2：水平滑动窗口

对每个起始行 $i$（$0 \le i \le m-k$），我们维护一个长度为 $n$ 的水平滑动窗口，窗口高度为 $k$，宽度为 $k$。

• 初始时，将 $k$ 列的信息合并到计数数组中
• 向右滑动时：
  • 移除左边一列（$j$ 列）的 $k$ 个元素
  • 加入右边一列（$j+k$ 列）的 $k$ 个元素
  • 更新 distinct

这样，每次滑动窗口的更新是 $O(k)$ 的，而不是 $O(k^2)$。

---

复杂度分析

• 子矩阵数量：$(m-k+1)(n-k+1)$
• 每次滑动更新：$O(k)$
• 总复杂度：$O(mnk)$

当 $m,n,k \le 3000$ 时，$mnk$ 最大约 $27 \times 10^9$，仍然可能超时，需要进一步优化。

---

进一步优化：二维差分思想

我们可以用另一种方法：

1. 先对每一行做水平长度为 $k$ 的滑动窗口，记录每个 $1 \times k$ 横条的不同元素个数（这步是 $O(mn)$）
2. 再对列做垂直长度为 $k$ 的滑动窗口，合并这些横条信息

但“不同元素个数”不能直接相加，需要更精细的维护。

---

最终可行方案：二维滑动窗口 + 全局计数数组

我们维护一个全局计数数组 cnt[x]，记录当前 $k \times k$ 窗口中每个数值的出现次数。

滑动步骤：

1. 初始构建第一个 $k \times k$ 窗口：$O(k^2)$
2. 向右滑动一列：
   • 移除左边一列的 $k$ 个元素（每个 cnt[x]--，如果变 0 则 distinct--）
   • 加入右边一列的 $k$ 个元素（每个 cnt[x]++，如果从 0 变 1 则 distinct++）
   • 复杂度 $O(k)$
3. 向下滑动一行：
   • 移除顶部一行的 $k$ 个元素
   • 加入底部一行的 $k$ 个元素
   • 复杂度 $O(k)$

这样，从 $(i,j)$ 窗口到 $(i,j+1)$ 窗口是 $O(k)$，从 $(i,j)$ 到 $(i+1,j)$ 也是 $O(k)$。

总复杂度：

• 初始构建：$O(k^2)$
• 第一行滑动：$(n-k)$ 次，每次 $O(k)$，共 $O(nk)$
• 向下移动：$(m-k)$ 次，每次对 $n-k+1$ 个窗口做 $O(k)$ 更新，共 $O(mnk)$

但注意，我们不需要对每个子矩阵都从头计算，而是利用滑动窗口性质，所以总操作次数是 $O(mn)$ 次 $O(k)$ 更新，即 $O(mnk)$。

---

实现细节

1. 计数数组大小
   题目说数值范围 $[1, C]$，$C \le 10^5$，所以数组开 $10^5+5$ 即可。

2. 内存与缓存
   尽量按行主序访问数据，提高缓存命中率。

3. 避免重复计算
   在滑动时，先移除旧列/旧行，再加入新列/新行。

---

代码框架（C++）

#include <bits/stdc++.h>
using namespace std;

const int MAXM = 3005;
const int MAXC = 100005;

int m, n, k;
int A[MAXM][MAXM];
int cnt[MAXC];  // 全局计数数组
int distinct;   // 当前窗口的不同元素个数

// 添加一个元素到窗口
void add(int x) {
    if (cnt[x] == 0) distinct++;
    cnt[x]++;
}

// 从窗口移除一个元素
void remove(int x) {
    cnt[x]--;
    if (cnt[x] == 0) distinct--;
}

int main() {
    scanf("%d%d%d", &m, &n, &k);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &A[i][j]);
        }
    }
    
    int max_div = 0;
    long long sum_div = 0;
    
    // 遍历所有可能的起始行
    for (int i0 = 0; i0 <= m - k; i0++) {
        // 重置计数数组
        memset(cnt, 0, sizeof(cnt));
        distinct = 0;
        
        // 构建第一个 k*k 窗口
        for (int i = i0; i < i0 + k; i++) {
            for (int j = 0; j < k; j++) {
                add(A[i][j]);
            }
        }
        
        // 第一行滑动
        for (int j0 = 0; j0 <= n - k; j0++) {
            // 记录当前窗口的多样性
            max_div = max(max_div, distinct);
            sum_div += distinct;
            
            // 向右滑动：移除左列，加入右列
            if (j0 < n - k) {
                for (int i = i0; i < i0 + k; i++) {
                    remove(A[i][j0]);
                    add(A[i][j0 + k]);
                }
            }
        }
        
        // 向下滑动：准备下一行起始
        if (i0 < m - k) {
            // 移除顶部一行，加入底部一行
            for (int j = 0; j < k; j++) {
                remove(A[i0][j]);
                add(A[i0 + k][j]);
            }
        }
    }
    
    printf("%d %lld\n", max_div, sum_div);
    return 0;
}

---

样例验证

对于样例：

3 5 2
1 5 3 3 3
4 1 3 3 4
4 2 4 4 3

$k=2$，子矩阵数量 $(3-2+1)\times(5-2+1) = 2\times4 = 8$。

手动计算多样性：

1. (0,0): {1,5,4,1} → {1,4,5} → 3
2. (0,1): {5,3,1,3} → {1,3,5} → 3
3. (0,2): {3,3,3,3} → {3} → 1
4. (0,3): {3,3,3,4} → {3,4} → 2
5. (1,0): {4,1,4,2} → {1,2,4} → 3
6. (1,1): {1,3,2,4} → {1,2,3,4} → 4
7. (1,2): {3,3,4,4} → {3,4} → 2
8. (1,3): {3,4,4,3} → {3,4} → 2

总和 = 3+3+1+2+3+4+2+2 = 20，最大值 = 4，与输出一致。

---

总结

这道题的关键在于：

1. 将二维滑动窗口分解为行列两次滑动
2. 用计数数组维护不同元素个数
3. 在滑动时只更新变化的列/行，避免重复计算