#4742. 「KTSC 2019 R1」新芽 题解

题目理解

这是一个二维滑动窗口统计问题：给定 $N \times N$ 的网格，每个格子有发芽数量 $V_{i,j}$，对于所有 $K \times K$ 的滑动窗口，计算：

[ \text{最大值} = \max_{\text{所有窗口}} \left| \text{总和} - \text{中位数} \times K^2 \right| ]

其中：

• 总和 = 窗口内所有值的和
• 中位数 = 窗口内所有值排序后的中间值（$K$ 为奇数）

核心算法

算法标签：滑动窗口 二维前缀和 计数排序 中位数快速计算

1. 算法框架

步骤1：二维前缀和预处理

vector<vector<llong>> V(n + 1, vector<llong>(n + 1, 0));
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        V[i][j] = V[i][j - 1] + V[i - 1][j] - V[i - 1][j - 1] + A[i][j];
    }
}

算法标签：二维前缀和 区域和查询

步骤2：滑动窗口计数

使用列方向的计数数组 Hcnt 来维护当前窗口每列的数值分布：

vector<vector<int>> Hcnt(n + 1, vector<int>(P + 1, 0));
// 初始化前k列的计数
for (int x = 0; x < k; ++x) {
    for (int y = 0; y <= n; ++y) {
        ++Hcnt[y][A[x][y]];
    }
}

步骤3：窗口滑动与中位数计算

for (int i = 0; i < n - k + 1; ++i) {
    // 垂直滑动：更新列计数
    for (int y = 0; y <= n; ++y) {
        --Hcnt[y][A[i    ][y]];
        ++Hcnt[y][A[i + k][y]];
    }
    
    // 水平滑动：维护当前窗口的完整计数
    for (int j = 0; j < n - k + 1; ++j) {
        // 更新水平方向的计数
        for (int p = 0; p <= P; ++p) {
            cnt[p] -= Hcnt[j    ][p];
            cnt[p] += Hcnt[j + k][p];
        }
        
        // 快速找到中位数
        int C = 0;
        for (int p = 0; p <= P; ++p) {
            C += cnt[p];
            if (C >= (k * k + 1) / 2) {
                D[i][j] = p;  // 中位数
                break;
            }
        }
    }
}

算法标签：滑动窗口优化 计数统计 中位数查找

步骤4：计算最大差值

llong ans = -1e18;
for (int i = 0; i < n - k + 1; ++i) {
    for (int j = 0; j < n - k + 1; ++j) {
        llong sum = V[i + k][j + k] - V[i + k][j] - V[i][j + k] + V[i][j];
        ans = max(ans, abs(sum - (llong)D[i][j] * k * k));
    }
}

算法正确性分析

为什么这样能高效计算中位数？

1. 数值范围小：$0 \leq V_{i,j} \leq 30$，可以用计数排序
2. 滑动窗口优化：
   • 垂直滑动时，只更新列的计数
   • 水平滑动时，通过列的计数快速更新窗口计数
3. 中位数查找：利用计数数组的累积和快速定位中位数

关键优化点

• 列计数分离：将二维窗口分解为列的一维计数
• 增量更新：滑动时只更新变化的列/行
• 前缀和加速：$O(1)$ 时间计算窗口和

复杂度分析

• 预处理：$O(N^2)$
• 垂直滑动：$O(N \times P)$ 每次，共 $O(N^2 \times P)$
• 水平滑动：$O(N^2 \times P)$
• 总复杂度：$O(N^2 \times P)$，其中 $P \leq 30$，实际为 $O(30N^2)$

算法标签总结

主要标签

• 滑动窗口 - 核心算法思想
• 计数排序 - 利用数值范围小的特性
• 二维前缀和 - 快速区域和计算

技术标签

• 中位数计算 - 通过累积计数快速查找
• 增量更新 - 滑动时高效维护统计信息
• 列分解 - 将二维问题分解为一维处理

优化标签

• $O(N^2)$算法 - 高效处理 $N \leq 2000$
• 常数优化 - 利用 $P \leq 30$ 的约束
• 空间换时间 - 使用多个辅助数组

数据结构标签

• 计数数组 - 核心数据结构
• 前缀和数组 - 快速求和
• 动态维护 - 滑动时更新统计信息

关键创新点

1. 列计数分离：将二维窗口的计数分解为每列的计数，支持高效滑动
2. 双重滑动：先垂直滑动更新列计数，再水平滑动组合列计数
3. 中位数快速定位：利用计数数组的单调性，$O(P)$ 时间找到中位数
4. 充分利用约束：利用数值范围小的特点，使用计数而非排序

样例验证

对于样例1：

• $N=6, K=3$
• 找到最大差值的窗口：中位数=0，总和=9，差值=9
• 算法通过滑动所有 $3 \times 3$ 窗口，计算每个窗口的中位数和总和，找到最大值

这个解法通过巧妙的计数维护和滑动窗口优化，高效解决了二维区域的中位数与平均值比较问题。