( m{0x01}) 关于左偏树
主要是整理自己想出来的几个梗
- (mathcal{To~be~(left) ~or~not ~to~be~(left), this~is ~a~question}) 左偏还是右偏，这是个问题。
- (Hell~!~Where~is~my~Left~Leaning~Tree?) 该死，我的左偏树向右偏了。
- 左偏树是1个log，右偏树也是1个log，那我左右都偏是不是就会更快！（恭喜你建出了一棵满二叉树）
- 讲个鬼故事：每棵树都是下偏树。
- ……编不出来了
呐，下面进入正题。左偏树，一种可以合并的堆状结构，支持(insert/remove/merge)等操作。稳定的时间复杂度在(Theta(log n))的级别。对于一个左偏树中的节点，需要维护的值有(dist)和(value)。其中(value)不必多说，(dist)记录这个节点到它子树里面最近的叶子节点的距离，叶子节点距离为(0)。
首先，他有以下几个喜闻乐见的性质：
- 一个节点的(value)必定（或小于）左、右儿子的(value) （堆性质）
- 一个节点的左儿子的(dist)不小于右儿子的(dist) （左偏性质）
- 一个节点的距离始终等于右儿子(+1)
那么这就可以推出以下性质：
- 推论：任何时候，节点数为(n)的左偏树，距离最大为(log (n+1)-1)
(Proof.)
对于一棵距离为定值(k)的树，点数最少时，一定是一棵满二叉树。这是显然的。因为对于每个节点，如果想要有最少的儿子，那么起码要做到左儿子的数量等于右儿子的数量。那么对于他的逆命题也是成立的——“若一棵左偏树的距离为(k)，则这棵左偏树至少有(2^{k+1}-1)个节点。”
所以会有$$n geq 2^{k+1}-1$$,$$log_2{(n+1)} geq k+1$$, $$log_2{(n+1)}-1 geq k$$ (mathcal{Q.E.D})
(emmm)这可是一个很美妙的性质啊。
( m{0x02}~~)基本操作
-
(Merge)
这是整个左偏树的重头戏，时间复杂度稳定在一个(log)，其主要思想就是不断把新的堆合并到新的根节点的右子树中——因为我们的右子树决定“距离”这个变量，而距离又一定保证在(~log~)的复杂度内，所以不断向右子树合并。
大体思路（以小根堆为例），首先我们假设两个节点(x)和(y)，(x)的根节点的权值小于等于(y)的根节点（否则(swap(x,y))），把(x)的根节点作为新树(Z)的根节点，剩下的事就是合并(x)的右子树和(y)了。
合并了(x)的右子树和(y)之后，(x)当(x)的右子树的距离大于(x)的左子树的距离时，为了维护性质二，我们要交换(x)的右子树和左子树。顺便维护性质三，所以直接(dist_x = dist_{rson(x)}+1).
inline int Merge(int x, int y){
if (!x || !y) return x + y ;
if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y) ;
rs = Merge(rs, y) ; if (S[ls].dis < S[rs].dis) swap(ls, rs) ;
S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1 ; return x ;
}
我们观察，我们是不断交替拆分右子树，由推论可得我们的距离不会大于$Theta(log(n_x+1))+Theta(log(n_y+1))-2 =O(log n_x+ log n_y) $
这个地方比较喜闻乐见的是需要存(root)，即需要路径压缩。不路径压缩的话，寻一次(rt)就是(Theta(n))的了，复杂度是不对的但似乎Luogu的模板，不路径压缩会更快
-
(Pop)
……(pop)的话，乱搞就好了(233)
inline void Pop(int x){ S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs) ; }
然后就是总代码：
#include <cstdio>
#include <iostream>
#define MAXN 150010
#define swap my_swap
#define ls S[x].Son[0]
#define rs S[x].Son[1]
using namespace std ;
struct Tree{
int dis, val, Son[2], rt ;
}S[MAXN] ; int N, T, A, B, C, i ;
inline int Merge(int x, int y) ;
int my_swap(int &x, int &y){ x ^= y ^= x ^= y ;}
inline int Get(int x){ return S[x].rt == x ? x : S[x].rt = Get(S[x].rt) ; }
inline void Pop(int x){ S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs) ; }
inline int Merge(int x, int y){
if (!x || !y) return x + y ; if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y) ;
rs = Merge(rs, y) ; if (S[ls].dis < S[rs].dis) swap(ls, rs) ; S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1 ; return x ;
}
int main(){
cin >> N >> T ; S[0].dis = -1 ;
for (i = 1 ; i <= N ; ++ i)
S[i].rt = i, scanf("%d", &S[i].val) ;
for (i = 1 ; i <= T ; ++ i){
scanf("%d%d", &A, &B) ;
if (A == 1){
scanf("%d", &C) ;
if (S[B].val == -1 || S[C].val == -1) continue ;
int f1 = Get(B), f2 = Get(C) ; if (f1 != f2) S[f1].rt = S[f2].rt = Merge(f1, f2) ;
}
else {
if(S[B].val == -1) printf("-1
") ;
else printf("%d
", S[Get(B)].val), Pop(Get(B)) ;
}
}
return 0 ;
}
( m{0x03}) 一点问题
问题大概就是路径压缩……
(LuoguP3377)很不负责任地处了数据，导致以下这份代码可以过：
using namespace std ;
struct Tree{
int dis, val, F, Son[2] ;
}S[MAXN] ;
int N, T, A, B, C, i ;
inline int Merge(int x, int y) ;
int my_swap(int &x, int &y){ x ^= y ^= x ^= y ;}
int Get(int x){ while(S[x].F) x = S[x].F ; return x ; }
inline void Pop(int x){ S[x].val = -1, S[ls].F = S[rs].F = 0, Merge(ls, rs) ; }
inline int Merge(int x, int y){
if (!x || !y) return x + y ; if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y) ;
rs = Merge(rs, y), S[rs].F = x ; if (S[ls].dis < S[rs].dis) swap(ls, rs) ; S[x].dis = S[rs].dis + 1 ; return x ;
}
int main(){
cin >> N >> T ; S[0].dis = -1 ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &S[i].val) ;
for (i = 1 ; i <= T ; ++ i){
scanf("%d%d", &A, &B) ;
if (A == 1){
scanf("%d", &C) ;
if (S[B].val == -1 || S[C].val == -1 || B == C) continue ;
int f1 = Get(B), f2 = Get(C) ; Merge(f1, f2) ;
}
else {
if(S[B].val == -1) printf("-1
") ;
else printf("%d
", S[Get(B)].val), Pop(Get(B)) ;
}
}
return 0 ;
}
一切都很正常，但问题在于他复杂度不对：
int Get(int x){ while(S[x].F) x = S[x].F ; return x ; }
这显然是个上界为(O(n))的函数……不寒而栗……
所以他是不对的，这组数据可以很好的卡掉（由巨佬小粉兔制作）。
所以应该用一个并查集维护。而我们在路径压缩之后，必须要在(pop)后，给(pop)掉的点一个指针指向新的根，所以：
inline int Get(int x){ return S[x].rt == x ? x : S[x].rt = Get(S[x].rt) ; }
inline void Pop(int x){ S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs) ; }
于是最后的代码：
#include <cstdio>
#include <iostream>
#define MAXN 150010
#define swap my_swap
#define ls S[x].Son[0]
#define rs S[x].Son[1]
using namespace std ;
struct Tree{
int dis, val, Son[2], rt ;
}S[MAXN] ; int N, T, A, B, C, i ;
inline int Merge(int x, int y) ;
int my_swap(int &x, int &y){ x ^= y ^= x ^= y ;}
inline int Get(int x){ return S[x].rt == x ? x : S[x].rt = Get(S[x].rt) ; }
inline void Pop(int x){ S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs) ; }
inline int Merge(int x, int y){
if (!x || !y) return x + y ; if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y) ;
rs = Merge(rs, y) ; if (S[ls].dis < S[rs].dis) swap(ls, rs) ; S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1 ; return x ;
}
int main(){
cin >> N >> T ; S[0].dis = -1 ;
for (i = 1 ; i <= N ; ++ i)
S[i].rt = i, scanf("%d", &S[i].val) ;
for (i = 1 ; i <= T ; ++ i){
scanf("%d%d", &A, &B) ;
if (A == 1){
scanf("%d", &C) ;
if (S[B].val == -1 || S[C].val == -1) continue ;
int f1 = Get(B), f2 = Get(C) ; if (f1 != f2) S[f1].rt = S[f2].rt = Merge(f1, f2) ;
}
else {
if(S[B].val == -1) printf("-1
") ;
else printf("%d
", S[Get(B)].val), Pop(Get(B)) ;
}
}
return 0 ;
}
( m{writter:Flower\_pks})