生活随笔
收集整理的這篇文章主要介紹了
【P3369 普通平衡树】 Splay
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
P3369
Splay 我的版本一開始是必須要Insert 一個最小值 和一個最大值的 不然前驅后繼 k大值會出鍋
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std
;#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))typedef pair
<int,int> pll
;
typedef long long ll
;
const int inf
= 0x3f3f3f3f;
const int _inf
= 0xc0c0c0c0;
const ll INF
= 0x3f3f3f3f3f3f3f3f;
const ll _INF
= 0xc0c0c0c0c0c0c0c0;
const ll mod
= (int)1e9+7;ll
gcd(ll a
,ll b
){return b
?gcd(b
,a
%b
):a
;}
ll
ksm(ll a
,ll b
,ll mod
){int ans
=1;while(b
){if(b
&1) ans
=(ans
*a
)%mod
;a
=(a
*a
)%mod
;b
>>=1;}return ans
;}
ll
inv2(ll a
,ll mod
){return ksm(a
,mod
-2,mod
);}
void exgcd(ll a
,ll b
,ll
&x
,ll
&y
,ll
&d
){if(!b
) {d
= a
;x
= 1;y
=0;}else{exgcd(b
,a
%b
,y
,x
,d
);y
-=x
*(a
/b
);}}
const int MAX_N
= 100025;
int ch
[MAX_N
][2],fa
[MAX_N
],cnt
[MAX_N
],sz
[MAX_N
],val
[MAX_N
],rev
[MAX_N
],root
,ncnt
;
int chk(int x
)
{return ch
[fa
[x
]][1] == x
;
}
void pushup(int x
)
{sz
[x
] = sz
[ch
[x
][0]] + sz
[ch
[x
][1]] + cnt
[x
];
}
void Rotate(int x
)
{int y
= fa
[x
],z
= fa
[y
],k
= chk(x
), w
= ch
[x
][k
^1];ch
[y
][k
] = w
;fa
[w
] = y
;ch
[z
][chk(y
)] = x
;fa
[x
] = z
;ch
[x
][k
^1] = y
;fa
[y
] = x
;pushup(y
);pushup(x
);
}
void Splay(int x
,int goal
= 0)
{while(fa
[x
]!=goal
){int y
= fa
[x
],z
= fa
[y
];if(z
!=goal
){if(chk(x
)==chk(y
)) Rotate(y
);else Rotate(x
);}Rotate(x
);}if(!goal
) root
= x
;
}
void Find(int x
)
{if(!root
) return;int cur
= root
;while(ch
[cur
][x
>val
[cur
]]&&x
!=val
[cur
]){cur
= ch
[cur
][x
>val
[cur
]];}Splay(cur
);
}
void Insert(int x
)
{int cur
= root
,p
= 0;while(cur
&&val
[cur
]!=x
){p
= cur
;cur
= ch
[cur
][x
>val
[cur
]];}if(cur
){cnt
[cur
]++;}else{cur
= ++ncnt
;if(p
) ch
[p
][x
>val
[p
]] = cur
;ch
[cur
][0] = ch
[cur
][1] = 0;val
[cur
] = x
;fa
[cur
] = p
;cnt
[cur
] = sz
[cur
] = 1;}Splay(cur
);
}
void pushdown(int x
)
{if(rev
[x
]){swap(ch
[x
][0],ch
[x
][1]);rev
[ch
[x
][0]] ^= 1;rev
[ch
[x
][1]] ^= 1;rev
[x
] = 0;}
}
int Kth(int k
)
{int cur
= root
;while(1){pushdown(cur
);if(ch
[cur
][0]&&k
<=sz
[ch
[cur
][0]]){cur
= ch
[cur
][0];}else if(k
>sz
[ch
[cur
][0]]+cnt
[cur
]){k
-= sz
[ch
[cur
][0]] + cnt
[cur
];cur
= ch
[cur
][1];}else return cur
;}
}
void Reverse(int l
,int r
)
{int x
= Kth(l
), y
= Kth(r
+2);Splay(x
);Splay(y
,x
);rev
[ch
[y
][0]] ^= 1;
}int pre(int x
)
{Find(x
);if(val
[root
]<x
) return root
;int cur
= ch
[root
][0];while(ch
[cur
][1]){cur
= ch
[cur
][1];}return cur
;
}
int suc(int x
)
{Find(x
);if(val
[root
]>x
) return root
;int cur
= ch
[root
][1];while(ch
[cur
][0]){cur
= ch
[cur
][0];}return cur
;
}
void Remove(int x
)
{int last
= pre(x
),next
= suc(x
);Splay(last
);Splay(next
,last
);int del
= ch
[next
][0];if(cnt
[del
]>1){cnt
[del
]--;Splay(del
);}else ch
[next
][0] = 0;
}
int main()
{Insert(_inf
);Insert(inf
);int n
,opt
,x
;scanf("%d",&n
);while(n
--){scanf("%d%d",&opt
,&x
);if(opt
==1){Insert(x
);}else if(opt
==2){Remove(x
);}else if(opt
==3){Find(x
);printf("%d\n",sz
[ch
[root
][0]]);}else if(opt
==4){printf("%d\n",val
[Kth(x
+1)]);}else if(opt
==5){printf("%d\n",val
[pre(x
)]);}else{printf("%d\n",val
[suc(x
)]);}}return 0;
}
總結
以上是生活随笔為你收集整理的【P3369 普通平衡树】 Splay的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
