模板题

维护一个长度为 $n$ 的数列 $a$,支持以下操作:

  1. $k$ 在区间 $[l,r]$ 内的排名。
  2. $[l,r]$ 区间内排名为 $k$ 的值。
  3. $a_{pos}\leftarrow v$。
  4. $k$ 在区间 $[l,r]$ 内的前驱。
  5. $k$ 在区间 $[l,r]$ 内的后继。

前驱/后继 定义为严格小于/大于自身且最大/最小的数。如果不存在,分别返回 $-inf$ 和 $inf$。

$1\leq n\leq 5\times 10^4$,$0\leq a_i,v\leq 10^8$。值域记为 $V$。


一直以为树套树是个很复杂的算法,但是如果允许 $2$ 操作时间复杂度 $O(\log^2n\log V)$ 的话可以有 普通线段树套平衡树(这里选用 $vector$)的简单写法;另外也有代码难度同样非常低的 值域线段树套普通线段树 做法。

先讲第一种及其好想且好写的 普通线段树套 $vector$ 的做法,以下说的 “平衡树” 也都代指这里的 $vector$。

对于线段树的每个区间 $[l,r]$,都把对应区间的数加入到这个结点的平衡树里,并且插入 $inf$ 以及 $-inf$。

先放出 $vector$ 部分的代码:

struct BT{
    #define find(a) lower_bound(s.begin(),s.end(),a) 
    #define finx(a) upper_bound(s.begin(),s.end(),a)
    vector<int> s;
    int operator [] (const int &i)const{return s[i];}
    void ins(int x){s.insert(find(x),x);}
    void del(int x){s.erase(find(x));}
    int rnk(int x){return find(x)-s.begin()-1;}
    int pre(int x){return (*(--find(x)));}
    int nxt(int x){return (*finx(x));}
}; 

$rnk(x)$ 操作返回的是比 $x$ 小的数的个数,减一是因为有 $-inf$ 的存在。

对于每个操作来分别考虑一下实现:

  1. 递归到线段树上,累加每个小区间里的 $rnk(k)$ 再加一就是排名。
  2. 这个操作是最花时间的,因为我貌似并不能找到更优的做法。$O(\log^2n\log V)$ 的做法是,二分一个值 $k$ 去跑操作 $1$ 即可。
  3. 和线段树单点修改一样,只需要把一路上的平衡树都删掉原来的值再插入新的值就好了。
  4. 区间内每个小区间的前驱取 $\max$。
  5. 区间内每个小区间的后继取 $\min$。

于是就和普通线段树没啥区别了...虽然跑的很慢,但是极其好写,代码长度 2.34kb


接下来是第二种值域线段树套普通线段树的写法,这样时空复杂度都是稳定两只 $\log$ 的。

考虑外层写值域线段树,把这个节点对应值域区间的数都插入到内层的线段树里,两层线段树都要写动态开点。

然后先来看区间 $k$ 大,这个就是经典的 Dynamic Rankings,只需要查询左儿子值域里数的个数就可以往下递归了。

支持 $O(\log^2n)$ 查区间 $k$ 大之后,再来看看区间 $rnk$ 操作,只需要累加区间内比 $k$ 小的数的个数就好了。

于是前驱可以用 $kth(rnk(k-1))$,后继可以用 $kth(rnk(k)+1)$,前面单点修改的做法也是一样的,于是也做完了,代码也同样好写。

代码长度 2.38kb

最后修改:2021 年 08 月 13 日
如果觉得我的文章对你有用,请随意赞赏