# 题解：这题是你自己出的

贡献：Codex（GPT-6）补齐加密规格，给出分块数对矩阵、二维树状数组和按值AVL位置树的组合算法，完成证明、实现与验证。

## 将区间分成整块和边角

设块长为 $B$ ，块数 $K=\lceil n/B\rceil$ .块 $b$ 中值 $v$ 的频数记为 $c_b(v)$ .维护矩阵

$$F_{b,d}=\sum_v c_b(v)c_d(v).$$

它表示第 $b$ 块与第 $d$ 块之间的有序相等数对数；对角线也按有序对计数，包含同一位置。用二维树状数组维护 $F$ 的单格增量和矩形和。

同时按值建立位置集合，使用带子树大小的AVL树支持某值在位置区间内出现多少次。节点以位置为键，修改时从旧值的树删除该节点，再插入新值的树。每块的值频数以及各值对应的树根使用有序映射。

## 查询分解

把第一个区间分为完整块部分 $I_0$ 与边角 $I_1$ ，第二个分为 $J_0,J_1$ .每份边角至多含 $2B$ 个位置。答案由三个互不重叠的集合组成：

1. $I_0\times J_0$ ：一次矩阵矩形和。
2. $I_1\times(J_0\cup J_1)$ ：逐个枚举第一区间边角位置，用该值的位置树统计整个第二区间。
3. $I_0\times J_1$ ：逐个枚举第二区间边角位置，在第一区间完整块覆盖的连续位置范围内统计。

此分解适用于重叠区间。不要在第三项查询整个第一区间，否则边角之间的数对会重复计数。没有完整块时，整个区间都是边角；处理一次即可。

## 修改矩阵

把块 $b$ 中一个值 $x$ 改为 $y$ .$x=y$ 时直接结束。对于 $d\ne b$ ，只有矩阵的第 $b$ 行和列改变，两个格子的增量都为

$$F_{b,d},F_{d,b}:\quad c_d(y)-c_d(x).$$

对角格只更新一次，其增量为

$$\bigl((c_b(x)-1)^2-c_b(x)^2\bigr)+\bigl((c_b(y)+1)^2-c_b(y)^2\bigr)=2(c_b(y)-c_b(x)+1).$$

这些频数取修改前的值。更新矩阵后再修改频数和位置树。

矩阵定义在初始化时成立，上述公式精确描述每次修改，因此一直成立。位置树由正确的插入、删除和子树大小维护保持准确。查询的三部分恰好划分所有有序数对，故输出正确。随后使用该答案解密下一行，归纳可知所有操作都按实际含义处理。

## 初始化、复杂度和实现

按值收集出现过的块及频数。某值出现于 $d_v$ 个块，就枚举这 $d_v^2$ 个块对建立矩阵。因为 $d_v\le K$ 且 $\sum_v d_v\le n$ ，工作量最多 $O(nK)$ ，而不必枚举所有位置对。

预处理 $O(n\log n+nK+K^2\log^2(K+1))$ .单次修改为 $O(K(\log(B+1)+\log^2(K+1))+\log n)$ ；查询为 $O(B\log n+\log^2(K+1))$ .空间 $O(n+K^2)$ .实现取 $B=400$ ；块长是时间折中参数，不影响正确性。

[std.cpp](std.cpp) 使用标准C++17，不依赖扩展顺序统计树。AVL树的旋转同时重算高度和子树大小。二维计数、答案和编码字段使用64位类型；负数解码显式按补码规则计算，避免依赖越界无符号到有符号转换。

逐查询扫描区间并统计频数是独立检查模型，但最坏 $O(nm)$ .只预存块对矩阵而没有位置秩结构，会使边角统计过慢；离线莫队不能预先获得尚未解密的查询。这些候选不作为当前完整范围的补充解法。

## 性能

正式数据每份运行五次并另测峰值。标准程序最慢中位数 0.707113 秒，峰值 30.11 MiB；按2倍取整到0.5秒，时限为 1.5 秒。 [环境说明](../../../docs/评测环境与性能.md)与[逐次测量](../../../docs/benchmark-R34.json)可供复现；其他环境需重新校准。