1. 题目

传送门= ̄ω ̄=

题目大意:

  • 给一个静态序列,再给出n个操作,每个操作为求一个区间内第k小的数字是多少

2. 题解

以前写过一个二分套线段树的题解:传送门= ̄ω ̄=(题目一样,就是那个有多组数据这个没有)

那个复杂度是$O(mlog_2^3n)$,比较慢

现在要讲的是主席树の做法,复杂度$O(mlog_2n)$

先讲思路:

首先,如果我们要查询某段区间内的第k小数,我们可以采用二分答案!每次二分一个答案,判断这个数字在区间内排第几。比如我们有一个序列:$43241$,我们查询区间$[2,5]$(即$3241$ )内排名第$2$的是谁。我们先二分一个答案,比如是$4$,发现$4$排名为$4$,所以答案比$4$小。再二分,比如是$1$ (鬼知道它怎么二分成这样的),发现$1$排名为$1$,所以答案比$1$大。这样下去就能找到最后答案为$2$!

介于这个思想,我们用主席树来实现!

先对原序列$a$(大小为$n$)进行排序、去重得到序列$h$,设序列$h$内元素个数为$tot$。我们对序列$a$的前缀$1,2,3,...,i(1\leq i\leq n)$分别建立一颗线段树(注意这里是线段树),一共有$n$颗线段树。第$i$颗线段树保存的是序列$h$中的每个元素各在$a$的前缀$1,2,3,...,i$中出现了多少次!

比如序列$a=45634$,那么$h=3456$,则线段树对应表如下:

第几颗 对应序列
1 0100(增加了数字4)
2 0110(增加了数字5)
3 0111(增加了数字6)
4 1111(增加了数字3)
5 1211(增加了数字4)

大概看懂了吧,我尽力惹QvQ

然后,比如我们要查询上面那个序列$a=45634$的区间$[2,5]$中的第$2$小的数字是谁,于是我们拿出第$2-1=1$颗线段树和第$5$颗线段树,如图:

t1

看懂了咩?其实就是俩维护区间和的线段树啊!(对应序列关系见上面的表格)

我们现在查第$2$小数嘛,于是我们先到俩线段树的根节点看。根节点的左右儿子分别对应着$h$序列的区间$[1,2]$和$[3,4]$,也就是$34$和$56$。可以看出来——在原序列$a=45634$的区间$[2,5]$(即$5634$)中,34一共出现了2次(3有1次,4有1次),正好是俩根节点的左儿子的权值之差($3-1=2$)。而56在区间$[2,5]$中一共出现了2次(5有1次,6有1次),正好是俩根节点的右儿子的权值之差($2-0=2$)。所以我们可以轻松得到:在区间$[l,r]$中,小于等于4的数字有2个,大于4的数字有2个。所以——我们就能知道——排名为$2$的数字一定是在根节点的左儿子对应的区间内的!(3和4)

然后我们进入根节点的左儿子,发现——它的左儿子是对应序列$h$中的3,它的右儿子对应的是序列$h$中的4,其中小于等于$3$的有$1-0=1$个,而大于$3$的有$2-1=1$个(注意观察上图中的线段树),因此排名为2的数字在它的右儿子节点对于的$h$序列区间中。

于是我们得到了最终答案——$h[2]=4$

这就是整个算法的全部原理。

由于我们需要$n$颗线段树,但是显然没有这么多空间、时间,所以我们用可持久化线段树——主席树

主席树原理我就不讲了,以后有空再总结一下了。

先安利一波教程(我在B站学算法QvQ):传送门= ̄ω ̄=

好吧,讲了这么多,放个代码: