自己口胡了一个数据结构题：
维护排列 \(s\)，支持如下操作：
- 查询 \(s_l,s_{l+1},\cdots,s_r\) 内大于等于 \(a\) 且小于等于 \(b\) 的第 \(k\) 小数；
- 交换 \(s_x\) 和 \(s_y\) 的值。
然后口胡了一下做法。
首先考虑没有修改操作的情况。考虑对值域分块，块长为 \(\sqrt n\)。维护 \(sum_{i,j}\) 表示 \(s_1\) 到 \(s_j\) 有多少个数落在第 \(i\) 块中。
那么显然预处理部分是可以 \(O(n\sqrt n)\) 搞的。
然后考虑查询。从 \(a\) 所在的块到 \(b\) 所在的块扫描一遍，每次通过 \(sum\) 求出 \(s_l\) 到 \(s_r\) 内有多少个数落在此块内，并累加到计数器 \(cnt\) 中。一旦 \(cnt\ge k\)，就说明答案在当前块中，直接退出，然后再扫描一遍当前块，就把答案搞出来了。
接下来考虑修改操作。考虑将一个操作拆解为在位置 \(x\) 上删除 \(s_x\)，添加 \(s_y\)，在位置 \(y\) 上删除 \(s_y\)，添加 \(s_x\) 这四个小操作。对于第一个小操作，设 \(s_x\) 所在的块为 \(p\)，那么需要将 \(sum_{p,x},sum_{p,x+1},\cdots,sum_{p,n}\) 全部减 \(1\)。剩下的三个同理。这个东西需要在 \(O(\sqrt n)\) 的时间以内解决，否则无法保证复杂度。
而进行查询操作时，将要 \(O(\sqrt n)\) 次使用 \(sum\) 的值。因此每次获取 \(sum\) 的时间只能为 \(O(1)\)。
考虑再用一个数据结构来维护 \(sum\) 数组。这个数据结构需要满足如下条件：
-
\(O(\sqrt n)\) 以内的区间加
-
\(O(1)\) 的单点查询
那么已经呼之欲出了：序列分块。
综上所述，可以在用 \(sum\) 数组维护值域分块以支持查询操作的同时，用序列分块来维护 \(sum\) 以支持修改操作。
这样就做到了总的 \(O(n\sqrt n)\) 的时间复杂度。
空间复杂度也为 \(O(n\sqrt n)\)。
在网上查了一下并没有发现类似的东西。于是我给这个东西取名叫做二次分块。