震驚，我竟然寫出了 fhq Treap#
先 % fhq 大佬
然後 % zxy 大佬
節點定義#
struct node
{
int w,siz,rdm;//權值，大小（包括自己），隨機數
int l,r;//左右兒子
} nd[MAXN];
特有操作#
fhq Treap 也被叫做無旋 Treap，它通過分裂與合併來維持平衡和堆的性質。
按值分裂#
將樹分成 x,y 兩棵樹，其中 x 中的元素都小於等於 w，y 中的元素都大於 w。
按地址傳參，調用後 x,y 為新樹的根。
開始寫的傳指針，但我太弱了一直沒寫對
void splitV(int p,int w,int &x,int &y)//p為當前更新到的節點
{
if(p==0)//邊界
{
x=y=0;
}
else
{
if(nd[p].w<=w)//當前節點比w小，那它和它的左子樹都屬於x
{
x=p;
splitV(nd[p].r,w,nd[p].r,y);//把x替換為nd[p].r，可以讓在右子樹中出現的比v小的節點接到x的右邊
}
else
{
y=p;
splitV(nd[p].l,w,x,nd[p].l);
}
update(p);//更新自身的size
}
}
按節點數量分裂#
眾所周知，中序遍歷一棵 BST 的結果是排好序的（然而我一開始並沒有想到這一點）。所以可以將節點分為前 k 大的和剩下的兩部分。
void splitS(int p,int num,int &x,int &y)
//把中序遍歷的前k個數單獨搞成一棵樹，剩下的是另一棵樹
//中序遍歷得到的是按大小順序排出的節點。
//因為會先訪問最小的。（先左然後中後右）
{
if(p==0)
{
x=y=0;
}
else
{
if(nd[nd[p].l].siz>=num)//左邊比要的大了
{
y=p;
splitS(nd[p].l,num,x,nd[p].l);//p的左兒子中有比p小，但比第num大大的。
}
else
{
x=p;
splitS(nd[p].r,num-nd[nd[p].l].siz-1,nd[p].r,y);//左邊小於num，找右邊第(num-nd[nd[p].l].siz-1)大的
}
update(p);//更新自身大小
}
}
合併#
已知 x 中所有元素小於等於 y 中所有元素
合併這兩棵樹並返回新根。
這裡體現了堆的性質
int merge(int x,int y)
{
if(x==0||y==0)
{
return x+y;//如果其中一個有值，會返回那個值
}
else
{
int tmp=0;
if(nd[x].rdm>=nd[y].rdm)//我猜這裡可以改成其他的不等關係
{
//x作為根
tmp=x;
nd[x].r=merge(nd[x].r,y);//合併右兒子與y，然後接到x右邊
}
else
{
tmp=y;
nd[y].l=merge(x,nd[y].l);
}
update(tmp);
return tmp;
}
}
平衡樹基操#
插入#
先新建一個節點
int newNd(int x)
{
++newp;
nd[newp].w=x;
nd[newp].rdm=rand();
nd[newp].siz=1;
return newp;
}
按權值分裂，再把新的節點和分開的兩棵樹按大小合併
void insert(int w)//
{
int x=0,y=0;
int p=newNd(w);
splitV(root,w,x,y);
x=merge(x,p);
root=merge(x,y);
}
刪除#
按 w-1,w 分成三棵
中間那棵所有節點權值都為 w
合併它的左右兒子，丟掉根，就刪除了一個節點
記得合回去
void remove(int w)
{
int x=0,y=0,z=0;
splitV(root,w,x,y);
splitV(x,w-1,x,z);
z=merge(nd[z].l,nd[z].r);
root=merge(merge(x,z),y); //z 的左右子樹合併即可刪掉一個v
}
求排名#
按值裂開，返回左兒子大小 + 1
int rank(int w)
{
int x=0,y=0,ret=0;
splitV(root,w-1,x,y);
ret=nd[x].siz+1;
root=merge(x,y);
return ret;
}
求第 k 大#
按排名裂開。。。。。
int kth(int k)
{
int x=0,y=0,z=0;
splitS(root,k,x,y);
splitS(x,k-1,x,z);
int ret=nd[z].w;
root=merge(merge(x,z),y);
return ret;
}
前驅#
按w-1裂開，找小的那棵樹裡最大的
int front(int w)
{
int x=0,y=0;
splitV(root,w-1,x,y);
int p=x;
while(nd[p].r)
{
p=nd[p].r;
}
root=merge(x,y);
return nd[p].w;
}
後繼#
按w裂開，找大的那棵樹裡最小的
int back(int w)
{
int x=0,y=0;
splitV(root,w,x,y);
int p=y;
while(nd[p].l)
{
p=nd[p].l;
}
root=merge(x,y);
return nd[p].w;
}
例題：洛谷 P3369 普通平衡樹#
就是上面那六個操作
區間翻轉（延遲標記）#
洛谷 P3835 文藝平衡樹
翻的時候打 lazytag
void fan(int x,int y)
{
int l,p,r;
split(root,y,l,r);
split(l,x-1,l,p);
nd[p].laz^=1;
root=merge(merge(l,p),r);
}
split,merge 和輸出時處理 lazytag
void split(int p,int siz,int &x,int &y)
{
if(p==0)
{
x=y=0;
return;
}
if(nd[p].laz)
{
push_down(p);
}
if(nd[nd[p].l].siz>=siz)
{
y=p;
split(nd[p].l,siz,x,nd[p].l);
}
else
{
x=p;
split(nd[p].r,siz-nd[nd[p].l].siz-1,nd[p].r,y);
}
update(p);
}
int merge(int x,int y)
{
if(x==0||y==0)
{
return x+y;
}
if(nd[x].rdm>nd[y].rdm)
{
if(nd[x].laz)push_down(x);
nd[x].r=merge(nd[x].r,y);
update(x);
return x;
}
else
{
if(nd[y].laz)push_down(y);
nd[y].l=merge(x,nd[y].l);
update(y);
return y;
}
}
void out(int p)
{
if(nd[p].laz)
{
push_down(p);
}
if(nd[p].l)
{
out(nd[p].l);
}
printf("%d ",nd[p].w);
if(nd[p].r)
{
out(nd[p].r);
}
}
下傳
void push_down(int p)
{
swap(nd[p].l,nd[p].r);
nd[p].laz=0;
nd[nd[p].l].laz^=1;
nd[nd[p].r].laz^=1;
}
可持久化#
非常簡單，只要在 split 和 merge 時為修改添加節點然後用 root 數組記錄版本就行了
然而。。。
我要瘋了。。。
以下是 split 和 merge。
void split(int p,int w,int &x,int &y)
{
if(p==0)
{
x=y=0;
}
else
{
int newn=++newp;
nd[newn]=nd[p];
if(nd[p].w<=w)
{
x=newn;
split(nd[x].r,w,nd[x].r,y);
}
else
{
y=newn;
split(nd[y].l,w,x,nd[y].l);
}
update(newn);
}
}
int merge(int x,int y)
{
if(x==0||y==0)
{ return x+y; }
int newn=++newp;
if(nd[x].rdm>nd[y].rdm)
{
nd[newn]=nd[x];
nd[newn].r=merge(nd[newn].r,y);
}
else
{
nd[newn]=nd[y];
nd[newn].l=merge(x,nd[newn].l);
}
update(newn);
return newn;
}