docs/misc/mo-algo-2dimen.md
二维莫队，顾名思义就是每个状态有四个方向可以扩展．
二维莫队每次移动指针要操作一行或者一列的数，具体实现方式与普通的一维莫队类似，这里不再赘述．这里重点讲块长选定部分．
记询问次数为 $q$，当前矩阵的左上角坐标为 $(x_1,\ y_1)$，右下角坐标为 $(x_2,\ y_2)$，取块长为 $B$．
那么指针 $x_1$ 移动了 $\Theta(q\cdot B)$ 次，而指针 $y_2$ 移动了 $\Theta(n^4\cdot B^{-3})$ 次．
所以只需令 $q\cdot B=n^4\cdot B^{-3}$，即 $B=n\cdot q^{-\frac 14}$ 即可．
注意这样计算 $B$ 的结果 可能为 $0$，注意特判．
最终，计算部分时间复杂度是 $\Theta(n^2\cdot q^{\frac 34})$，加上对询问的排序过程，总时间复杂度为 $\Theta(n^2\cdot q^{\frac 34}+q\log q)$．
???+ note "BZOJ 2639 矩形计算" 输入一个 $n\times m$ 的矩阵，矩阵的每一个元素都是一个整数，然后有 $q$ 个询问，每次询问一个子矩阵的权值．矩阵的权值是这样定义的，对于一个整数 $x$，如果它在该矩阵中出现了 $p$ 次，那么它给该矩阵的权值就贡献 $p^2$．
数据范围：$1\leq n,\ m\leq 200$，$0\leq q\leq 10^5$，$|$ 矩阵元素大小 $| \leq 2\times 10^9$．
??? note "解题思路" 先离散化，二维莫队时用一个数组记录每个数当前出现的次数即可．
??? note "示例代码"
cpp --8<-- "docs/misc/code/mo-algo-2dimen/mo-algo-2dimen_1.cpp"
???+ note "洛谷 P1527 [国家集训队] 矩阵乘法" 给你一个 $n\times n$ 的矩阵，$q$ 次询问，每次询问一个子矩形的第 $k$ 小数．
数据范围：$1\leq n\leq 500$，$1\leq q\leq 6\times 10^4$，$0\leq a_{i,j}\leq 10^9$．
首先和上一题一样，需要离散化整个矩阵．但是需要注意，本题除了需要对数值进行分块，还需要对数值的值域进行分块，才能求出答案．
这里还需要用到奇偶化排序进行优化，具体内容请见 普通莫队算法．
对于本题而言，时间限制不那么宽，注意代码常数的处理．取的块长计算值普遍较小，$n,\ q$ 都取最大值时块长大约在 $11$ 左右，可以直接设定为常数来节约代码耗时．
??? note "示例代码"
cpp --8<-- "docs/misc/code/mo-algo-2dimen/mo-algo-2dimen_2.cpp"