@fuheimao
2015-08-21T12:27:06.000000Z
字数 1833
阅读 667
Treap
腹黑猫
数据结构
#include "iostream"
#include "cstdlib"
using namespace std;
struct Node{
Node* Child[2];
int Key;
int Priority;
int Size;
void Maintain(){
Size = 1;
if (Child[0] != NULL) Size += Child[0]->Size;
if (Child[1] != NULL) Size += Child[1]->Size;
}
};
Node* Root = NULL;
int Size(Node* A){
return (A == NULL ? 0 : A->Size);
}
Node* Merge(Node* A, Node* B){
if (A == NULL) return B;
if (B == NULL) return A;
if (A->Priority < B->Priority){
A->Child[1] = Merge(A->Child[1], B);
A->Maintain();
return A;
}else{
B->Child[0] = Merge(A, B->Child[0]);
B->Maintain();
return B;
}
}
pair<Node*, Node*> Split(Node* A, int K){
if (A == NULL) return pair<Node*, Node*>(NULL, NULL);
pair<Node*, Node*> DoubleRoot;
if (K <= Size(A->Child[0])){
DoubleRoot = Split(A->Child[0], K);
A->Child[0] = DoubleRoot.second;
A->Maintain();
DoubleRoot.second = A;
}else{
DoubleRoot = Split(A->Child[1], K - Size(A->Child[0]) - 1);
A->Child[1] = DoubleRoot.first;
A->Maintain();
DoubleRoot.first = A;
}
return DoubleRoot;
}
int FindKth(int K){ //第K小
pair<Node*, Node*> Left = Split(Root, K - 1);
pair<Node*, Node*> Right = Split(Left.second, 1);
Node* Kth = Right.first;
Root = Merge(Merge(Left.first, Kth), Right.second);
return Kth->Key;
}
int Rank(Node* Top, int Key){ //Key为第几大
if (Top == NULL) return 0;
return (Key < Top->Key ? Rank(Top->Child[0], Key) : Rank(Top->Child[1], Key) + Size(Top->Child[0]) + 1);
}
void Insert(int Key){
Node* NewNode = new Node();
NewNode->Key = Key;
NewNode->Priority = rand();
NewNode->Child[0] = NewNode->Child[1] = NULL;
NewNode->Maintain();
int Pos = Rank(Root, Key);
pair<Node*, Node*> DoubleRoot = Split(Root, Pos);
Root = Merge(Merge(DoubleRoot.first, NewNode), DoubleRoot.second);
}
void Remove(int Key){
int K = Rank(Root, Key);
pair<Node*, Node*> Left = Split(Root, K - 1);
pair<Node*, Node*> Right = Split(Left.second, 1);
Root = Merge(Left.first, Right.second);
}
void Modify(int KeyBefore, int KeyAfter){
Remove(KeyBefore);
Insert(KeyAfter);
}
int main(int argc, char const *argv[]){
Insert(100);
Insert(500);
Insert(300);
Insert(200);
Remove(100);
cout << Rank(Root, 300);
return 0;
}