警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P1527」矩阵乘法 - 整体二分

题意

传送门:洛谷 P1527 - 矩阵乘法

给你一个 \(n \times n\) 的矩阵,每次查询一个子矩阵的 \(k\) 小数。

\(n \le 5 \times 10^2, q \le 6 \times 10^4\)

解法

注意到这题数据范围非常小,我们可以用主席树很轻松地解决。

但是这样太套路了。考虑整体二分。

首先我们将矩阵中所有的数写成修改的形式。例如 \(a_{i, j}\) 等价于将 \((i, j)\) 修改为 \(a_{i, j}\)

然后我们这样进行整体二分:

  • 计算查询编号区间为 \(p[l1, r1)\)、修改编号区间为 \(q[l2, r2)\) 的答案
  • 执行 \([l2, mid2)\) 的修改操作
  • 对于每个 \(i \in [l1, r1)\)\(p_i\)
    • 如果它的答案是 \([l2, mid2)\) 之间的某次修改操作的操作数,那么分到 \(p1\)
    • 如果它的答案是 \([mid2, r2)\) 之间的某次修改操作的操作数,那么分到 \(p2\)
  • 撤销 \([l2, mid2)\) 的修改操作(清空数据结构)
  • 递归计算 \(p1, q[l2, mid2)\)\(p2, q[mid2, r2)\)

执行修改操作的部分使用二维树状数组。修改 \((i, j)\) 等价于树状数组中将 \((i, j)\) 加一。

那么如果某个查询对应的子矩阵在经过 \([l2, mid2)\) 的查询之后,子矩阵和 \(\ge k\),那么就分到 \(p1\),否则分到 \(p2\)

代码