区间 rank 的 N 种解法，你都会了吗

问题：给定长度为 $n$ 的序列 $a$，进行 $m$ 次询问，每次询问区间 $[l,r]$ 中的数的第 $k$ 大/小是多少。 下面统一以第 $k$ 大为例，默认离散化后值域为 $[1,n]$。 **你出生了**，你学会了冒泡/插入/选择排序，于是你每次询问都排一下序，取出倒数第 $k$ 的数，再还原回去，复杂度 $O(mn^2)$。 **你上了幼儿园**，你知道有一种 $\text{STL}$ 叫做 $\text{sort}$，于是你的复杂度降到了 $O(mn\log n)$。 **你上了小学**，你学会了一种东西叫做分治，于是你分治做每个询问，你是用一个 $G(l,r,k)$ 表示要求出 $[l,r]$ 的第 $k$ 大，然后你类似快速排序，把一半的小于阈值的数排在左边，递归进入，于是复杂度 $O(m(n+\dfrac n2+\dfrac n4+\ldots))=O(mn)$ **你有要好的同学**，告诉你有一种 $\text{STL}$ 叫做 $\text{nth\_element}$，这样代码量大大减小 **你参加了OI社团**，你知道了一种思想叫做从值域考虑，于是你把区间里的数在值域上进行一个映射，然后倒着扫，扫到一个数就 $k\leftarrow k-1$，$k=0$ 的时候输出这个数就行了，复杂度 $O(mn)$。 **你上了初中**，你学会了线段树，于是你使用线段树思想。 用一个线段树节点表示，这个区间的数排序后的集合，可以用 $\text{vector}$ 简单维护，每次 $\text{pushup}$ 时把两个子节点归并一下。 这样就预处理好了，时空复杂度 $O(n\log n)$。 对于询问，你考虑 $\text{binary\_search}$，每次二分一个数 $\text{mid}$，求有多少区间内的数大于它，对于这个求有多少区间内的数大于它，考虑在掏出线段树上的 $O(\log n)$ 个节点，在上面的 $\text{vector}$ 上面再二分，询问复杂度 $O(m\log^3n)$。[实现POJ2104](https://raw.githubusercontent.com/shangkelingxiang/shangkelingxiang.github.io/gh-page/luoguribao/%230.cpp) **准备NOIP的时候**，你学习了可持久化线段树。 结合差分的思想，我们先考虑一种优雅的暴力。 考虑在值域上建 $n$ 棵线段树，第 $i$ 个线段树表示 $[1,i]$ 的数在值域上的映射。 然后每次询问的时候，只需要取出第 $r$ 棵线段树和第 $l-1$ 棵线段树，做一下差，然后在线段树上二分即可。 但是空间显然会爆，于是考虑每一次修改只会修改 $O(\log n)$ 个节点，于是你适当地在原来的基础上更改即可，时间复杂度 $O((n+m)\log n)$，空间复杂度 $O(n\log n)$。[实现P3834](https://raw.githubusercontent.com/shangkelingxiang/shangkelingxiang.github.io/gh-page/luoguribao/%231.cpp) **你上了高中**，学习了平衡树，发觉可持久化线段树好像可以结合初中时的思想再做。你拿平衡树换掉 $\text{vector}$，（感谢 Missa 提醒，之前的版本说的有点不清楚），用线段树维护值域，比方说线段树上表示 $[l,r]$ 的节点表示值域在 $[l,r]$ 中间的值的位置集合构成的平衡树，然后在线段树上二分，每次 $O(\log n)$ 查询左子节点有多少数大于当前数，决定往哪里跳，时间复杂度 $O((n+m)\log^2n)$，空间复杂度 $O(n\log n)$，但是好像还支持修改了？！[实现P3834，但是拿 $\text{vector}$ 当平衡树了](https://raw.githubusercontent.com/shangkelingxiang/shangkelingxiang.github.io/gh-page/luoguribao/%232.cpp) **你去做 Ynoi 了**，入门了分块，于是你考虑分块。 把序列分块，$blo$ 为块长，一共 $n/blo$ 个块，每个块存这个块内数排序后的结果，每次询问时二分答案 $mid$，然后大块用二分得出多少数大于 $mid$，散块枚举出多少数大于 $mid$。空间复杂度大突破！$O(n)$！时间复杂度 $O(n\log n+m\log n(\dfrac {n\log n}{blo}+blo))$，由均值不等式，$blo$ 取 $\sqrt{n\log n}$ 时复杂度最优为 $O(n\log n+m\log n\sqrt{n\log n})$。 但是[支持区间加啦？？](https://www.luogu.com.cn/problem/P5356)。[实现P5356](https://raw.githubusercontent.com/shangkelingxiang/shangkelingxiang.github.io/gh-page/luoguribao/%233.cpp) 但是[支持单点插入啦？？](https://www.luogu.com.cn/blog/Peterprpr/p4278-dai-cha-ru-ou-jian-k-xiao-zhi-ji-lu)。 **做了太多 Ynoi，还不会 Binary Search**，于是你深究 $\text{Binary Search}$。 考虑只有一组询问的时候怎么做。 你可以二分值域，结合值域树状数组 $O(\log^2n)$ 解决。 于是你考虑一个神奇的东西。 如何骗数据点？ 有一个题，输入只有一个 $n$，现在告诉你数据大小是 $1\le n\le10^9$，让你通过 $\text{assert}$ 函数求出所有数据点。 你先 $\text{assert(n<=5e8)}$，把 $\text{RE}$ 的点记在左手上，把别的点记在右手上。 这样你就知道你左手上表示的点都是 $>5e8$ 的，右手上的点都是 $\le 5e8$ 的。 然后你递归下去就行了，不会超过 $\log1e9$ 次，这就是 整体 二分。 同理我们再看这个题，你使用一个 $solve(1,n,1,m)$ 函数表示我即将处理 $[1,m]$ 这些询问，并且我保证这些询问的答案是在 $[1,n]$ 阈值内的。 你猜测你的这些询问和 $mid$ 相比大还是小，于是把这些询问归类，归为两类递归下去。时间复杂度 $O(n+m\log^2n)$，空间复杂度 $O(n)$，好像也可以修改了。[实现P3834](https://raw.githubusercontent.com/shangkelingxiang/shangkelingxiang.github.io/gh-page/luoguribao/%234.cpp)[实现P2617](https://raw.githubusercontent.com/shangkelingxiang/shangkelingxiang.github.io/gh-page/luoguribao/%236.cpp) **你机房里的同学教会了你莫队**，于是你考虑莫队做法。 考虑移动端点的时候用一个树状数组同时维护这个区间在值域上的体现，然后你询问的时候二分出第 $k$ 大，空间复杂度 $O(n)$，时间复杂度 $O(n\sqrt m\log n+m\log^2n)$。 **你又做了很多 Ynoi，时光飞逝**，于是你考虑纯正根号做法。 你不仅对值域分块，还对序列分块。 记 $g_{i,j}$ 表示前 $i$ 块值域为 $j$ 的有几个 $(i\in[1,\sqrt n],j\in[1,n])$。 记 $G_{i,j}$ 表示前 $i$ 块值域在 $j$ 值域块里的有几个 $(i\in[1,\sqrt n],j\in[1,\sqrt n])$。 对于询问 $[l,r],k$，记 $l$ 在第 $p$ 块，$r$ 在第 $q$ 块，且令 $p<q$（其余暴力即可）。 把 $[l,R_p],[L_q,r]$ 里的数处理成 $f_i$，表示 $i(i\in[1,n])$ 在这两个区间里出现过几次，同时也处理出一个 $F_i(1\in[1,\sqrt n])$，表示这两个区间里的数在 $i$ 值域块上出现了几次（$L_x,R_x$ 表示第 $x$ 块的左右端点）。 于是你可以通过 $O(1)$ 查询 $[l,r]$ 中 $x$ 出现了几次以及 $[l,r]$ 中 $x$ 值域块有几个。 然后遍历值域块，如果 $k$ 大于当前值域块中的数字的出现次数，就减掉到下一块，否则停下，遍历这一块。 时空复杂度 $O(n\sqrt n)$，好像还支持[区 间 神 秘 修 改](https://www.luogu.com.cn/problem/P4119)。[实现P3834](https://raw.githubusercontent.com/shangkelingxiang/shangkelingxiang.github.io/gh-page/luoguribao/%237.cpp) **Ynoi 分块题你刷穿了，你已经年近中年，开始研究 $\log$ Ynoi。** 你再优化你初中时整出来的那玩意儿。 你同时维护一个节点，它里面有多少数被划分到左边，有多少数被划分到右边，然后也能在线段树上二分，时空复杂度与主席树相同，你了解了这个东西叫划分树。 中年了，码力不行，没有码。 **你老了** 研究了中庸之道。 莫队的时候移动端点的数目是 $O(n\sqrt m)$ 量级的，但是询问只有 $O(m)$ 量级，于是你平衡复杂度，想办法整一个 $O(1)$ 修改，$O(\sqrt n)$ 查询的东西来平衡时间复杂度，于是你值域分块，用一个 $g_x$ 表示 $x$ 被修改了多少，用一个 $G_x$ 表示 $x$ 值域块被修改了多少，然后查询时查询值域块和散块，修改时只需修改 $G$ 和 $g$，时间复杂度 $O(n\sqrt m+m\sqrt n)$，空间复杂度 $O(n)$。[实现P3834](https://raw.githubusercontent.com/shangkelingxiang/shangkelingxiang.github.io/gh-page/luoguribao/%238.cpp) **入土前**，你发现这个分块**好像**可以逐块处理减少空间复杂度。 不 你合上了双眼 都是我对数据结构的爱啊 $$\huge{\texttt{End}}$$ _____________________________ ### 后记 突然对这个东西感触很深，做个小整理，还要继续赶路。 没有讲很多种解法，只讲到了 $14$ 种，还包括一些很拉很初级的算法。 但还是感觉区间 $\text{rank}$ 对各种思想有一个全面的概述，适合更多初学者。 包括了对数据结构离线，在线，动态，静态的介绍，也用浅显易懂的方式讲解，包含了对复杂度优化的思想。 避免了 zzmg 的东西。 彩蛋： 原标题：浅 谈 区 间 r a n k 的 1 1 4 5 1 4 种 解 法 文中原来的一句话：把序列分成 $blo$ 个块，一共 $n/blo$ 个块 ComeIntoPower：@peterwuyihong 感谢投稿，这也太臭了，有点不敢放上去（