驚き、私は fhq Treap を書いた#
先 % fhq 大佬
そして % zxy 大佬
ノード定義#
struct node
{
int w,siz,rdm;//重み、サイズ（自身を含む）、ランダム数
int l,r;//左と右の子
} nd[MAXN];
特有操作#
fhq Treap は無回転 Treap とも呼ばれ、分裂と結合によってバランスとヒープの特性を維持します。
値による分裂#
木を x,y の 2 つの木に分けます。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に置き換え、右部分木に出現するw以下のノードをxの右に接続します
}
else
{
y=p;
splitV(nd[p].l,w,x,nd[p].l);
}
update(p);//自身のサイズを更新
}
}
ノード数による分裂#
ご存知の通り、BST の中間順遍歴の結果はソートされています（しかし最初はこれを思いつきませんでした）。したがって、ノードを前 k 大と残りの 2 つの部分に分けることができます。
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)//左側が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 のすべての要素以下であることが知られています。
これらの 2 つの木を結合し、新しい根を返します。
ここでヒープの特性が現れます。
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;
}
重みで分裂し、新しいノードと分けた 2 つの木をサイズで結合します。
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 で 3 つに分けます。
中央の木のすべてのノードの重みは w です。
その左右の子を結合し、根を捨てることで、1 つのノードを削除します。
忘れずに戻します。
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の左右の子を結合することで1つの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 普通平衡木#
上記の 6 つの操作です。
区間反転（遅延マーク）#
洛谷 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;
}