动态区间第k大的一种$O(nlog^2n)$的树套树解法

题意:

​ 给定一个序列,有“将一个数修改为另一个”的操作,和询问“[l,r]区间内的第k小值是几”的询问。要求在1s内对一个长$10^4$的序列完成$10^4$组修改和询问。

思路:

1.
​ 我最先想到的树套树的思路是:线段树套Splay。

​ 线段树的每一个区间[l,r]定义为原序列的[l,r]中的数字组成的排序Splay。这样,对于每个修改操作,我们对$logn$棵包含了这个位置的Splay删除一个数,添加一个数即可。对于每个询问操作[l,r],我们需要二分答案x,再在logn棵恰好组成[l,r]区间的Splay中查询x的排名。

​ 由于线段树有logn层,每层的所有Splay合并后恰为一个完整的原序列,所以空间复杂度为O(nlogn)的。

​ 经过上面的分析可知:修改复杂度为$O(nlog^2n)$,查询为$O(nlog^3n)$。实践证明可以通过所有测试点。洛谷最慢测试点340ms.
2.
​ 第二种思路,即本文终点介绍的思路,两种操作都是$O(nlog^2n)$的,只是还需要对所有出现过的数字离散化。

​ 刚才,我们的线段树对应的是区间,Splay对应的是值。如果互换一下呢?

​ 现在线段树是建立在离散化后的实数域上的。线段树区间[l,r]定义为原序列中值属于[l,r]的所有值的下标的排序Splay。即:将值属于[l,r]的所有位置提取为一个新的序列,保存在这个Splay里。

​ 对于修改操作,我们依旧修改$logn$棵Splay。如果我们将a[i]修改为b,则将所有的线段树节点$[l,r](l\leq a[i]\leq r)$中的Splay中删除i。同时向所有的线段树节点$[l,r](l\leq b\leq r)$中的Splay添加i。故一次修改操作的复杂度为$O(log^2n)$。

​ 对于查询操作,注意到这棵线段树是支持前缀和的。即实数区间[l,r]内的数x$(a\leq x \leq b)$的个数等于[1,r]内的个数减[1,l-1]内的个数(这里的x就是原序列的下标)。所以我们只需要在树上二分即可。如果现在我们确定了k小值一定在实数区间[a,b]内,那么如果[a,(a+b)/2]内的Splay中满足上述条件的节点小于k,则k小值一定在[(a+b)/2+1,b]内,反之同理。这样的查询操作只需要对logn个线段树节点进行查询,故一次询问的时间复杂度为$O(log^n)$。

​ 实践证明可以通过所有测试点,洛谷最慢测试点92ms.

细节问题

​ 这种方法虽然省去了一个log,但是其代码量却比之前多了一个log。

​ 以下是一些需要注意的地方:

  • 离散化不但要离散原序列的值,也要离散修改出的值。
  • 在最初插入节点时最好使用类似线段树建树一样的归并方式,这样可以降低常数。实践证明不这样洛谷最慢点为296ms.
  • 最好不要用这种方法因为我打了200行。