块状数组超级兵器：区间动态排名问题

上期回顾：https://www.cnblogs.com/ofnoname/p/18994725，https://www.cnblogs.com/ofnoname/p/19034861
我们学习了如何把一维数组“分块”，在每块里维护额外信息，从而在查询与修改之间取得平衡。通过解决区间众数问题，我们还发现分块不只是切切数组，它还能在块的层次上维护结构化的信息。
动态区间第 k 小 / 排名问题

这次，我们要解决了另一个经典的问题是维护一个随时要查询排名的数组：

• 数组是可变的，存在单点修改操作。
  
• 我们需要在区间上回答一系列查询，包括：某段区间的第 k 小、某值的排名和某数前驱 / 后继
  
• 而且值域可能很大。
  

参考题目：https://www.luogu.com.cn/problem/P3380。虽然题目名称是“树套树”，但是块状数组也是正确的做法。
相比基础的“求和/最值”类问题，这里涉及排名、顺序统计、前驱后继，已经非常接近数据结构的“核心需求”。能解决它，意味着我们真正把块状数组推向了“动态序列查询”的前沿。
为了应对挑战，我们会展示两种思路：

• 位置分块 + 块内有序数组
  使用最原始暴力的思路。借助块内排序和二分，我们可以高效实现排名、前驱后继，并通过“二分值域 + 排名”解决第 k 小。
  
• 位置分块 + 值域分块（两层分块）
  再进一步，把值域也分块，像之前的区间众数问题一样，预处理数字的出现个数，并维护两层前缀计数。彻底摆脱值域二分。
  

思路一：位置分块 + 块内有序数组

将数组分块切割的同时，每个块再维护一个有序数组。这样一来：

• 修改时：在块内删除旧值、插入新值（同样也更改相应的有序数组）。
  
• 查询时：中间完整块可以挨个用二分在有序数组里快速处理。
  

操作拆解

区间内某值的排名

查询排名即查找 < z 的数字的个数，边界块直接计数，中间块每一块都二分查找一次。假定 \(B\) 为块长，\(T = \lceil\frac NB\rceil\)，总复杂度\(O(B + T\log B)\)，若块长取根号，则为\(O(\sqrt n\ \log n)\)
[code]auto get_rank = [&](int x, int y, int z) {    int p = b[x], q = b[y], res = 1;    if (q - p