题目理解

我们有一个 $H \times W$ 的网格，每个格子放着 J、O、I 三种道具之一。需要统计满足以下条件的四元组 $(i, j, k, l)$ 的数量：

• $1 \le i < k \le H$
• $1 \le j < l \le W$
• $(i, j)$ 位置是 J
• $(i, l)$ 位置是 O
• $(k, j)$ 位置是 I

几何解释：这相当于在网格中找一个"L"形，左上角是 J，右上角是 O，左下角是 I，右下角可以是任意字符。

暴力解法分析

最直接的方法是枚举所有可能的四元组：

1. 枚举 $i$ 从 $1$ 到 $H$
2. 枚举 $j$ 从 $1$ 到 $W$
3. 枚举 $k$ 从 $i+1$ 到 $H$
4. 枚举 $l$ 从 $j+1$ 到 $W$
5. 检查条件并计数

复杂度：$O(H^2W^2)$，对于 $H, W \leq 3000$，这是完全不可行的（约 $8\times 10^{13}$ 次操作）。

关键观察

1. 重新组织枚举顺序

注意到四元组实际上由两个行 $i, k$ 和两个列 $j, l$ 确定。我们可以改变枚举顺序：

固定 $i$ 和 $k$（两行），然后统计在这两行上满足条件的列对 $(j, l)$ 的数量。

2. 条件分解

对于固定的两行 $i$ 和 $k$，条件变为：

• 第 $i$ 行第 $j$ 列是 J
• 第 $i$ 行第 $l$ 列是 O
• 第 $k$ 行第 $j$ 列是 I

这意味着对于列 $j$，必须同时满足：

• 第 $i$ 行第 $j$ 列 = J
• 第 $k$ 行第 $j$ 列 = I

对于列 $l$，只需要满足：

• 第 $i$ 行第 $l$ 列 = O

3. 计数方法

对于固定的两行 $i$ 和 $k$：

• 设 $A$ = 满足「第 $i$ 行是 J 且第 $k$ 行是 I」的列 $j$ 的集合
• 设 $B$ = 满足「第 $i$ 行是 O」的列 $l$ 的集合

那么对于这两行的贡献就是 $|A| \times |B|$，因为：

• 每个 $j \in A$ 和每个 $l \in B$ 且 $j < l$ 都构成一个有效四元组
• 由于 $j < l$ 的限制，实际上贡献是 $|A| \times |B|$（因为我们可以任意配对）

注意：这里 $j < l$ 的限制实际上不影响计数，因为对于固定的 $A$ 和 $B$，$j < l$ 的对数就是 $|A| \times |B|$（我们可以重新标记列号）。

高效算法

1. 预处理

为了快速计算对于任意两行 $i, k$ 的 $|A|$ 和 $|B|$，我们可以预处理：

• cnt_JI[i][k]：对于行 $i$ 和 $k$，满足「第 $i$ 行是 J 且第 $k$ 行是 I」的列数
• cnt_O[i]：第 $i$ 行中 O 的数量

2. 算法步骤

1. 预处理：

   • 对于每个行 $i$，预处理该行每个字符的位置信息
   • 或者直接记录每行中 J、O、I 的数量和位置

2. 计算答案：

   • 枚举 $i$ 从 $1$ 到 $H$
   • 枚举 $k$ 从 $i+1$ 到 $H$
   • 对于每对 $(i, k)$，计算：
     • $A$ = 同时满足「第 $i$ 行是 J」且「第 $k$ 行是 I」的列数
     • $B$ = 第 $i$ 行中 O 的数量
     • 贡献 = $A \times B$
   • 累加所有贡献

3. 复杂度分析

• 预处理：$O(HW)$
• 主循环：枚举 $O(H^2)$ 对行，每对行需要 $O(W)$ 时间计算 $A$
• 总复杂度：$O(H^2W)$

对于 $H, W \leq 3000$，这仍然是 $9\times 10^9$ 级别，可能超时。

进一步优化

1. 优化 $A$ 的计算

我们可以预处理一个二维数组 JI[i][k]，表示行 $i$ 和行 $k$ 中满足「第 $i$ 行是 J 且第 $k$ 行是 I」的列数。

但是直接存储所有 $H^2$ 对会超内存（$3000^2 = 9\times 10^6$ 个整数，约 36MB，可以接受）。

计算方法：

• 对于每个列 $j$，找出所有满足「第 $i$ 行是 J 且第 $k$ 行是 I」的行对 $(i, k)$
• 这可以通过预处理每列中 J 和 I 的位置来实现

2. 最终高效算法

1. 预处理：

   • O_count[i]：第 $i$ 行中 O 的数量
   • 对于每个列 $j$，记录：
     • rows_J[j]：该列中为 J 的行集合
     • rows_I[j]：该列中为 I 的行集合

2. 计算 JI 矩阵：

   • 初始化 JI[i][k] = 0 对所有 $i < k$
   • 对于每个列 $j$：
     • 对于 rows_J[j] 中的每个行 $i$
     • 对于 rows_I[j] 中的每个行 $k > i$
     • JI[i][k]++

3. 计算答案：

   • 对于所有 $i < k$，答案 += JI[i][k] × O_count[i]

3. 复杂度分析

• 预处理：$O(HW)$
• 计算 JI 矩阵：每个列 $j$ 的复杂度是 |\text{rows_J}[j]| \times |\text{rows_I}[j]| 的总和
• 最坏情况下，如果某列全是 J 和 I，复杂度可能达到 $O(H^2W)$

但实际上，由于每列中 J 和 I 的数量通常远小于 $H$，实际运行效率较高。

总结

这道题的核心在于通过巧妙的组合计数方法，将四维枚举问题转化为二维预处理问题：

1. 问题转化：将四元组计数转化为行对与列对的组合计数
2. 关键观察：固定两行后，条件分解为独立的列条件
3. 组合计数：使用乘法原理计算行对贡献
4. 预处理优化：通过预处理行列信息来加速计算

通过深入分析问题结构，我们找到了避免直接四重枚举的高效算法，这在处理大规模网格计数问题时是非常典型的优化思路。