口胡树套树

· · 个人记录

树套树不是一种的特定的算法，而是用来解决问题的方法，和动态规划有点相似

不妨看一个例题

也就是 P3380二逼平衡树

先介绍一种写法：线段树套平衡树

线段树内维护的就是区间 [L,R] 内部所有值构成的平衡树，而这个空间复杂度是O(nlogn)的

对于前驱，我们用线段树找区间，在每个节点寻找一次前驱，然后取这些点的最大值即可，后继同理

对于给定k，求其排名，直接在每个区间求 kth

而求给定排名，求其数字的，我们直接二分一个数字，找是否比其小的数字个数

而对于修改，就是删除点，加入点的过程

除了给定排名为 O(log^3n) 的情况，其他都是O(log^2n)

（这可太暴力了）

然后还有一种思路，那就是树状数组套动态开点权值线段树

我们大概都知道在静态区间是可以维护权值线段树，来维护排名的，但是本题多了一个修改操作，而这个修改应该会影响到后面的权值线段树

这看起来就不是很好做了

但是我们似乎想起来树状数组可以维护前缀和的情况，而权值线段树维护kth 恰好也是一个前缀和过程

于是我们就用树状数组维护前缀和过程即可

\text{Nothing can change my determination}

求个数(a_i,b_i,c_i)\leq(a_j,b_j,c_j)

首先分三个关键字排序，这样就先消掉一维

接下来，来了一个数字 b_i,c_i 我们二维偏序的时候可以考虑一个二维数组，我们维护它的前缀和就可以做出来，但我们发现空间装不下

而树状数组套动态开点权值线段树可以完美解决这个问题，我们首先用线段树套动态开点权值线段树来理解这个过程：在外部线段树找到询问的 [ 1 , b_i-1] 区间，在内部线段树中维护寻找 [1,c_i-1]

我们知道 线段树 和 树状数组 在本质上是差不多的

我们就用树状数组来维护