题解

问题分析

题目要求模拟一个 $N \times N$ 网格的填色过程，其中：

• 第一列固定为 $A_1, A_2, \dots, A_N$
• 第一行固定为 $B_1, B_2, \dots, B_N$
• 其余格子 $(i,j)$ 的颜色由 $(i-1,j)$ 和 $(i,j-1)$ 中颜色编号较大的决定

需要找出出现次数最多的颜色（编号相同时输出编号最大的）。

关键观察

1. 填色规律：每个格子 $(i,j)$ 的颜色实际上是第一列前 $i$ 个元素和第一行前 $j$ 个元素中的最大值

   $$\text{color}(i,j) = \max(\max_{1 \le k \le i} A_k, \max_{1 \le l \le j} B_l) $$

2. 单调性：从左上到右下，颜色值单调不减

3. 区域划分：网格会被划分成若干个矩形区域，每个区域内所有格子颜色相同

算法思路

单调栈 + 区域统计：

1. 离散化：将颜色值映射到 $0 \sim m-1$ 的整数
2. 按颜色值降序处理：从大到小处理每种颜色，确保先处理可能覆盖大面积的颜色
3. 动态维护边界：
   • 用变量 r 记录当前已处理的最小行索引
   • 用变量 c 记录当前已处理的最小列索引
4. 区域计数：
   • 如果当前颜色在第一列的第 i 行，它会影响从第 i 行到最后一行，第 c 列到最后一列的矩形区域
   • 如果当前颜色在第一行的第 j 列，它会影响从第 r 行到最后一行，第 j 列到最后一列的矩形区域

核心代码逻辑

// 按颜色值从大到小排序处理
std::ranges::sort(o, [&](int i, int j) -> bool {
    return a[i] > a[j];
});

int r = n, c = n;
for (int i : o) {
    cnt[a[i]] += i > 0;  // 第一行第一列的交点只算一次
    
    if (0 < i && i < n && i < r) {  // 第一列的新最大值
        cnt[a[i]] += 1ll * (r - i) * (c - 1);
        r = i;
    } else if (n < i && i < 2 * n && i - n < c) {  // 第一行的新最大值
        cnt[a[i]] += 1ll * (r - 1) * (c - i + n);
        c = i - n;
    }
}

复杂度分析

• 离散化：$O(N \log N)$
• 排序：$O(N \log N)$
• 区域统计：$O(N)$
• 总复杂度：$O(N \log N)$

算法步骤

1. 读入 $N$ 和数组 $A, B$
2. 将颜色值离散化
3. 创建索引数组并按颜色值降序排序
4. 初始化边界 r = c = N
5. 按颜色从大到小处理：
   • 更新该颜色影响的矩形区域
   • 调整边界 r 或 c
6. 找到出现次数最多且编号最大的颜色
7. 输出结果

算法标签

• 离散化
• 单调栈思想
• 区域计数
• 贪心算法
• 排序处理