一种“用平衡树修改自己”的算法

最近在考试时发现可以用 FHQ-Treap

O(n\log^2n)

做一些事情，觉得很有趣，就记录下来。若有与他人重复，还请提醒。

起因是考场上遇到了这样一个问题：

有两个数列 $a,c$ ，满足 $c_i<i$ 。从前往后对于每个位置，求出一个数对 $p_i=(a_i,d_i)$ ，其中 $d_i\in [c_i,i)$ ，要求 $d_i$ 是 $[c_i,i)$ 中 $p_i$ 最小的位置。对于两个数对排序方式是：先比较 $a_i,a_j$ 的大小，若相同比较 $p_{d_i},p_{d_j}$ 的大小。要求时间复杂度为 $O(n\log^2n)$ 。

容易发现，假如我们在求解

p_i

的时候，已经知道了前

i-1

个位置的

p

数组排名，那么我们可以用线段树简单维护每个

d_i

。难点在于如何排序。

容易发现当你塞入一个新的数对

p_i

时，比

p_i

大的数对排名会

+1

。因此考虑可以进行区间加的 FHQ-Treap。但是难点在于如何利用平衡树自身的排名进行分裂。因为假如我们只按照每个位置上记录的排名进行排序，可能会出现懒标记暂未下放的情况；而分裂操作会破坏树结构，因此普通平衡树中的查排名操作也无法实施。

考虑不下放标记，而让节点通过向上一步一步爬的方式找标记。定义 getnum(x) 函数表示我们从

x

开始，一直执行向父亲跳和给

x

的

num

加上当前点的懒标记值的操作，最终得出的数就是这个位置的真实排名，代码如下：

CPP

inline int getnum(int x){
	int re=num(x);x=fa(x);
	while(x) re+=fl(x),x=fa(x);
	return re;
}

由于平衡树深度为

O(\log n)

，所以这一操作的时间复杂度即为

O(\log n)

。由于

split

操作本身就有一个

\log

，所以现在

split

的总时间复杂度为

O(\log^2n)

。代码如下：

CPP

inline int getnum(int x){
  	int re=num(x);x=fa(x);
  	while(x) re+=fl(x),x=fa(x);
  	return re;
}
inline bool operator<(suf x,suf y){
  	return x.fs!=y.fs?x.fs<y.fs:getnum(x.ls)<getnum(y.ls);
}
inline void push_up(int x){
    sz(x)=sz(ls(x))+sz(rs(x))+1;
}
inline void down(int x,int k){
    fl(x)+=k,num(x)+=k;
}
inline void push_down(int x){
    down(ls(x),fl(x)),down(rs(x),fl(x)),fl(x)=0;
}
inline void split(int x,suf v,int &a,int &b,int af,int bf){
    if(!x){a=b=0;return;}push_down(x);
    if(v<val(x)) split(ls(x),v,a,ls(b=x),af,x),fa(x)=bf;
    else split(rs(x),v,rs(a=x),b,x,bf),fa(x)=af;push_up(x);
}
inline int merge(int x,int y){
    if(!x||!y) return x|y;push_down(x),push_down(y);
    if(rk(x)<rk(y)) return rs(x)=merge(rs(x),y),fa(rs(x))=x,push_up(x),x;
    return ls(y)=merge(x,ls(y)),fa(ls(y))=y,push_up(y),y;
}

这样我们就可以用总时间复杂度

O(n\log^2n)

的做法 AC 这个问题了。由于时间复杂度非均摊，所以理论上可以做可持久化。另外，本题理论上可以将区间加改为区间反转等更复杂的区间操作。

一种“用平衡树修改自己”的算法

文章操作

相关推荐

评论

一种“用平衡树修改自己”的算法