0
12

Treap

操作

非旋转Treap

-define表+struct，请对照此表理解代码-

``````#define lson t[x].ls
#define rson t[x].rs
#define si t[x].size
#define ra t[x].ran
#define lss t[t[x].ls].size
#define va t[x].val
//-------------------------
struct node
{
int val, size, ls, rs, ran;
}t[100001];

``````

新建节点

``````inline void newnode(int &x, int val)
{
++tot;
t[tot].size=1;
t[tot].val=val;
t[tot].ran=rand();
t[tot].ls=t[tot].rs=0;
x=tot;
}
``````

分裂

``````void split(int x, int &l, int &r, int val)
{
if(!x)
{
l = r = 0;
return;
}
if(va <= val) l = x, split(t[x].rs, t[l].rs, r, val);//当前值比val小或等于val，则将它与它的左子树全部划分到第一棵树，继续寻找它的右子树
else r = x, split(t[x].ls, l, t[r].ls, val);//反之，则将它与它的右子树划分到第二棵树，寻找它的左子树
pushup(x);//不要忘记更新size
}
``````

合并

``````void merge(int &x, int a, int b)
{
if(!a||!b)
{
x = a + b;
return;
}
if(t[a].ran < t[b].ran) x = a, merge(t[x].rs, t[a].rs, b);//随机值在这里用，用来在合并时维护堆的性质
else x = b, merge(t[x].ls, a, t[b].ls);
pushup(x);//更新！
}
``````

插入

``````void insert(int val)
{
int x = 0, y = 0, z = 0;
newnode(z, val);
split(root, x, y, val - 1);
merge(x, x, z);
merge(root, x, y);
}
``````

删除

``````void del(int val)
{
int x = 0, y = 0, z = 0;
split(root, x, y, val);
split(x, x, z, val - 1);
merge(z, t[z].ls, t[z].rs);//这里是只删除一个的操作，全部删除请忽略本行和下一行
merge(x, x, z);
merge(root, x, y);
}
``````

询问排名

``````void ask_rank(int v)
{
int x = 0, y = 0;
split(root, x, y, v - 1);
cout << si + 1;
merge(root, x, y);
}
``````

询问第k小

``````void ask_num(int x, int kth)
{
while(lss + 1 != kth)
{
if(lss >= kth) x = lson;
else kth -= (lss + 1), x = rson;
}
cout << va;
}
``````

前驱

``````void ask_fr(int v)
{
int x = 0, y = 0;
split(root, x, y, v - 1);
merge(root, x, y);
}
``````

后继

``````void ask_ba(int v)
{
int x = 0, y = 0;
split(root, x, y, v);
merge(root, x, y);
}
``````

总代码（以Luogu P3369为例）

``````#include <bits/stdc++.h>
#define lson t[x].ls
#define rson t[x].rs
#define si t[x].size
#define ra t[x].ran
#define lss t[t[x].ls].size
#define va t[x].val
using namespace std;
int root;
namespace treap
{
int tot;
struct node
{
int val, size, ls, rs, ran;
}t[100001];
inline void newnode(int &x, int val)
{
++tot;
t[tot].size=1;
t[tot].val=val;
t[tot].ran=rand();
t[tot].ls=t[tot].rs=0;
x=tot;
}
inline void pushup(int x)
{
si = lss + rss + 1;
}
void split(int x, int &l, int &r, int val)
{
if(!x)
{
l = r = 0;
return;
}
if(va <= val) l = x, split(t[x].rs, t[l].rs, r, val);
else r = x, split(t[x].ls, l, t[r].ls, val);
pushup(x);
}
void merge(int &x, int a, int b)
{
if(!a||!b)
{
x = a + b;
return;
}
if(t[a].ran < t[b].ran) x = a, merge(t[x].rs, t[a].rs, b);
else x = b, merge(t[x].ls, a, t[b].ls);
pushup(x);
}
void insert(int val)
{
int x = 0, y = 0, z = 0;
newnode(z, val);
split(root, x, y, val - 1);
merge(x, x, z);
merge(root, x, y);
}
void del(int val)
{
int x = 0, y = 0, z = 0;
split(root, x, y, val);
split(x, x, z, val - 1);
merge(z, t[z].ls, t[z].rs);
merge(x, x, z);
merge(root, x, y);
}
{
int x = 0, y = 0;
split(root, x, y, v - 1);
cout << si + 1;
merge(root, x, y);
}
{
while(lss + 1 != kth)
{
if(lss >= kth) x = lson;
else kth -= (lss + 1), x = rson;
}
cout << va;
}
{
int x = 0, y = 0;
split(root, x, y, v - 1);
merge(root, x, y);
}
{
int x = 0, y = 0;
split(root, x, y, v);
merge(root, x, y);
}
};
using namespace treap;
int main()
{
int n;
cin >> n;
srand(2005);
while(n--)
{
int x, y;
cin >> x >> y;
if(x == 1) insert(y);
else if(x == 2) del(y);
else if(x == 3) ask_rank(y), cout << endl;
else if(x == 4) ask_num(root, y), cout << endl;
else if(x == 5) ask_fr(y), cout << endl;
else if(x == 6) ask_ba(y), cout << endl;
}
return 0;
}
``````

<