题解 P3377 【【模板】左偏树（可并堆）】
皎月半洒花
2019-01-27 16:21:28
此处其余的题解复杂度不是很对，下面着重说一种比较靠谱的方案。
安利原[$blog$](https://www.cnblogs.com/pks-t/p/10326682.html)
那么问题大概就是他们没有路径压缩……
[$LuoguP3377$](https://www.luogu.org/problemnew/show/P3377)很不负责任地处了数据，导致以下这份代码可以过：
```cpp
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\n") ;
else printf("%d\n", S[Get(B)].val), Pop(Get(B)) ;
}
}
return 0 ;
}
```
一切都很正常，但问题在于他复杂度不对：
```cpp
int Get(int x){ while(S[x].F) x = S[x].F ; return x ; }
```
这显然是个上界为$O(n)$的函数……不寒而栗……
所以他是不对的，[这组数据](https://www.luogu.org/discuss/show/96561)可以很好的卡掉（由巨佬小粉兔制作）。
所以应该用一个并查集维护。而我们在路径压缩之后，必须要在$pop$后，给$pop$掉的点一个指针指向新的根（否则就会直接断掉），所以：
```cpp
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) ; }
```
于是最后的代码：
```cpp
#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\n") ;
else printf("%d\n", S[Get(B)].val), Pop(Get(B)) ;
}
}
return 0 ;
}
```
$\rm{writter:Flower\_pks}$