核心内容摘要
地址层级省略不再怕：MGeo轻松识别‘杭州’和‘杭州市’
目录标题以静态区间第k kk小为例。
首先假装你会归并树。
归并树是啥其实就是对归并排序的过程建树。
先建立一个线段树再自底向上归并求出每个节点对应的区间[ l , r ] [l,r][l,r]的所有元素构成的有序序列。
归并树可以慢速二维数点。
具体地我们要查区间[ l , r ] [l,r][l,r]有多少个≤ x \le x≤x的数可以直接找到每个线段树节点对节点上的序列二分一下。
时间复杂度是O ( log 2 n ) \mathcal{O}(\log^2 n)O(log2n)的。
要是直接拿这玩意二分求区间第k kk小可以做到高贵的O ( log 2 n log V ) \mathcal{O}(\log^2 n\log V)O(log2nlogV)复杂度这也太菜了。
究其原因是没有利用好归并树能做二维数点。
不妨换维将下标与值域互换相当于求值域在[ l , r ] [l,r][l,r]内的从左到右第k kk个数。
这就成功把要二分的东西放到了线段树维护的维度上那么可以把二分换成线段树二分做到O ( log n log V ) \mathcal{O}(\log n\log V)O(lognlogV)。
还能再给力一点吗注意到换维过后值域是O ( n ) \mathcal{O}(n)O(n)的了如果能O ( n ) \mathcal{O}(n)O(n)地对同一层处理出来每个数前面有几个数那么就能再去掉一个log n \log nlogn。
于是我们开始思考怎么干这个事情。
方便起见把线段树换成01trie \text{01trie}01trie这样可以省掉一些讨论。
现在每一层的元素个数是O ( n ) \mathcal{O}(n)O(n)值域也是O ( n ) \mathcal{O}(n)O(n)我们当然希望能把同一层的所有数都搓到一起。
于是不妨将所有左子树扔到最前面右子树扔到最后面然后把序列拼起来。
大概是这样这个大概叫“蝴蝶变换”。
方便起见把左子树方向称为红色右子树方向称为蓝色。
这个树的结构就可以扔掉了因为我只需要知道一个位置前面有几个蓝色元素就能直接推出它在蝴蝶变换后会到哪个地方。
现在在线段树二分上的过程可以写成这样从第一层开始。
计算[ l , r ] [l,r][l,r]之间的红色元素数量。
若个数≥ k \ge k≥k则往红色子树走。
否则往蓝色子树走。
我们甚至只需要知道元素个数所以每一层做一个前缀和即可。
代码大概长这样inlineintkth(intl,intr,intk){intres0;l--;for(inti29;~i;i--){intqlb[i][l],qrb[i][r],c(r-qr)-(l-ql);if(ck)l-ql,r-qr;elseres|1i,k-c,lp[i]ql,rp[i]qr;}returnres;}其中b i b_ibi是第i ii层的前缀和p i p_ipi是第i ii层的红色元素个数。
这样我们就做到了O ( log V ) \mathcal{O}(\log V)O(logV)查询。
还能再再再给力一点吗时间复杂度上很难优化了但是空间O ( n log V ) \mathcal{O}(n\log V)O(nlogV)还是不够看。
发现我们只要算1 11的个数可以压个位空间复杂度做到O ( n log V w ) O ( n ) \mathcal{O}\left(\frac{n\log V}{w}\right)\mathcal{O}(n)O(wnlogV)O(n)。
然后你就吊打主席树了。
恭喜你发明了小波矩阵structBitset{intn;vectorpairull,intb;Bitset(){}Bitset(vectorulla){n(a.size()