二维莫队，顾名思义就是每个状态有四个方向可以扩展．

二维莫队每次移动指针要操作一行或者一列的数，具体实现方式与普通的一维莫队类似，这里不再赘述．这里重点讲块长选定部分．

## 块长选定

记询问次数为 $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)$．

## 例题 1

???+ note "[BZOJ 2639 矩形计算](https://hydro.ac/p/bzoj-P2639)"
    输入一个 $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"
    ```

## 例题 2

???+ note "[洛谷 P1527 \[国家集训队\] 矩阵乘法](https://www.luogu.com.cn/problem/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$．

首先和上一题一样，需要离散化整个矩阵．但是需要注意，本题除了需要对数值进行分块，还需要对数值的值域进行分块，才能求出答案．

这里还需要用到奇偶化排序进行优化，具体内容请见 [普通莫队算法](../misc/mo-algo.md#普通莫队的优化)．

对于本题而言，时间限制不那么宽，注意代码常数的处理．取的块长计算值普遍较小，$n,\ q$ 都取最大值时块长大约在 $11$ 左右，可以直接设定为常数来节约代码耗时．

??? note "示例代码"
    ```cpp
    --8<-- "docs/misc/code/mo-algo-2dimen/mo-algo-2dimen_2.cpp"
    ```
