二维莫队
二维莫队，顾名思义就是每个状态有四个方向可以扩展．
二维莫队每次移动指针要操作一行或者一列的数，具体实现方式与普通的一维莫队类似，这里不再赘述．这里重点讲块长选定部分．
块长选定
记询问次数为 𝑞q
，当前矩阵的左上角坐标为 (𝑥1, 𝑦1)(x1, y1)，右下角坐标为 (𝑥2, 𝑦2)(x2, y2)，取块长为 𝐵B．
那么指针 𝑥1x1 移动了 Θ(𝑞 ⋅𝐵)Θ(q⋅B) 次，而指针 𝑦2y2 移动了 Θ(𝑛4 ⋅𝐵−3)Θ(n4⋅B−3) 次．
所以只需令 𝑞 ⋅𝐵 =𝑛4 ⋅𝐵−3q⋅B=n4⋅B−3，即 𝐵 =𝑛 ⋅𝑞−14B=n⋅q−14 即可．
注意这样计算 𝐵B 的结果 可能为 00，注意特判 ．
最终，计算部分时间复杂度是 Θ(𝑛2 ⋅𝑞34)Θ(n2⋅q34)，加上对询问的排序过程，总时间复杂度为 Θ(𝑛2 ⋅𝑞34 +𝑞log𝑞)Θ(n2⋅q34+qlogq)．
例题 1
输入一个 𝑛 ×𝑚n×m 的矩阵，矩阵的每一个元素都是一个整数，然后有 𝑞q 个询问，每次询问一个子矩阵的权值．矩阵的权值是这样定义的，对于一个整数 𝑥x，如果它在该矩阵中出现了 𝑝p 次，那么它给该矩阵的权值就贡献 𝑝2p2．
数据范围：1 ≤𝑛, 𝑚 ≤2001≤n, m≤200，0 ≤𝑞 ≤1050≤q≤105，|| 矩阵元素大小 | ≤2 ×109|≤2×109．
解题思路
先离散化，二维莫队时用一个数组记录每个数当前出现的次数即可．
示例代码
---|---
## 例题 2
[洛谷 P1527 [国家集训队] 矩阵乘法](https://www.luogu.com.cn/problem/P1527)
给你一个 𝑛 ×𝑛n×n 的矩阵，𝑞q 次询问，每次询问一个子矩形的第 𝑘k 小数．
数据范围：1 ≤𝑛 ≤5001≤n≤500，1 ≤𝑞 ≤6 ×1041≤q≤6×104，0 ≤𝑎𝑖,𝑗 ≤1090≤ai,j≤109．
首先和上一题一样，需要离散化整个矩阵．但是需要注意，本题除了需要对数值进行分块，还需要对数值的值域进行分块，才能求出答案．
这里还需要用到奇偶化排序进行优化，具体内容请见 [普通莫队算法](../mo-algo/#普通莫队的优化)．
对于本题而言，时间限制不那么宽，注意代码常数的处理．取的块长计算值普遍较小，𝑛, 𝑞n, q 都取最大值时块长大约在 1111 左右，可以直接设定为常数来节约代码耗时．
示例代码
---|---
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：HeRaNO, megakite, Molmin, Tiphereth-A 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用