White_Wat
2023-12-26 22:40:30
所以没人看我为什么要写啊是因为我要用来复习啊那没事了
Treap = Tree + Heap
即 Treap 是同时满足二叉堆 Heap 和二叉搜索树的平衡树
满足 Heap 的堆值随机来使得平衡树的状态随机（大概率不会退化成链）
大部分操作代码里都打注释了（不会就看AgOH的讲解）
（算了还是讲一下吧）
Fhq Treap 就是一种不用旋转的平衡树，时间复杂度
因为其不旋转（使用分裂和合并替代）但却能保持 Treap 的性质，使其思想复杂度 大大减小！
维护 Fhq Treap 的有两个主要操作，分裂和旋转：
就是一整棵树裂开来
分裂操作分两种：按值分裂和按大小分裂，按大小分裂文艺平衡树里再说。
按值分裂即将一颗树按照给定值
就是将两棵树合并成为一颗树。因为合并时树
那接下来就是利用分裂与合并来进行平衡树操作，例题是- P3369 【模板】普通平衡树。~（代码里都有注释了那这里就偷懒不写了）~
下面是全是注释的代码（好丑要被嫌弃了）
还有就是代码细节很多写的时候不要漏掉+1-1什么的（难道只有我太蒻了每次写都会出错O.o）
#include<iostream>
#include<random>
using namespace std;
const int N=1e5+5;
struct node{
int l,r; //左右子树
int val,key;//值和索引，索引用于模拟二叉堆
int size; //子树大小
}fhq[N];
int cnt,root; //这里是树的大小和根节点
mt19937 rnd(210828); //幸运随机码
inline int newnode(int val)
{
fhq[++cnt].val=val; //这个不用解释了吧...
fhq[cnt].key=rnd(); //随机索引！
fhq[cnt].size=1; //最开始的时候树的大小肯定是1捏~
return cnt; //每次返回新创建的节点编号，方便合并
}
//这个是用来更改树大小的捏~
inline void update(int now)
{
fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
//树的值 <= val 归 一棵树 (x)
//树的值 > val 归 另一棵树 (y)
/*
虽然是分裂成树x与是y，但是传入的x与y可以说是当前节点now
在分裂后可以与树x或者树y连接的编号捏~
*/
inline void split(int now,int val,int &x,int &y)
{
if(!now) x=y=0;
else
{
if(fhq[now].val<=val)
{
x=now; //根据搜索二叉树定义此时所有的左子树val都 <=val，所以分裂右子树
split(fhq[now].r,val,fhq[now].r,y); //分裂右子树
}
else
{
y=now; //根据搜索二叉树定义此时所有的右子树val都 >val，所以分裂左子树
split(fhq[now].l,val,x,fhq[now].l); //分裂左子树
}
update(now);//修改树大小
}
}
//树x中所有值都<=树y中所有值（这个在传入时就要注意捏~）
inline int merge(int x,int y)
{
if(!x||!y) return x+y; //如果x或者y不存在就返回另外一个
if(fhq[x].key>fhq[y].key) //索引随机，符号可以是 任意 ( > >= < <= )
//所以这里是类似大根堆
{
/*
树x的根在树y根的上方
因为树x中的值小于树y中的值，所以树y一定在树x的右方
所以树y在树x的右下方
所以是树x右子树和y合并
*/
fhq[x].r=merge(fhq[x].r,y); //传入的树值第一个小第二个大
update(x); //更新新的树大小
return x;
}
else
{
/*
树x的根在树y根的下方
因为树x中的值小于树y中的值，所以树y一定在树x的右方
所以树y在树x的右上方
所以是树x和树y左子树合并
*/
fhq[y].l=merge(x,fhq[y].l);
update(y); //更新新的树大小
return y;
}
}
/*
插入操作：
先按照值val分裂成树x和树y
合并时要满足前参<=后参
所以先合并树x和新节点，再与y树合并
*/
int x,y,z;
inline void ins(int val)
{
split(root,val,x,y);
root=merge(merge(x,newnode(val)),y);
}
/*
删除操作：
先按照值val分裂成树x和树z
再按照值val-1分裂树x成树x和树y
现在树y上值全为val
去掉树y根节点即可（合并树y左子树和右子树）
*/
inline void del(int val)
{
split(root,val,x,z);
split(x,val-1,x,y);
y=merge(fhq[y].l,fhq[y].r);
root=merge(merge(x,y),z);
}
/*
查询排名操作：
先按照val-1分裂成树x和树y
此时val的排名就是树x的大小+1( fhq[x].size+1 )
*/
inline void get_rank(int val)
{
split(root,val-1,x,y);
printf("%d\n",fhq[x].size+1);
root=merge(x,y);
}
/*
查询排名的值：
从根节点开始
如果左子树的大小大于等于排名，那么就在左子树上找
如果左子树大小+1等于排名，那么就是当前结点
否则就是在右子树，是右子树里排名为[当前排名 - (左子树大小+1)]
（这个多减去的1是算上当前节点排名）
*/
inline void get_num(int rank)
{
int now=root;
while(now)
{
if(fhq[fhq[now].l].size+1==rank)
break;
else if(fhq[fhq[now].l].size>=rank)
now=fhq[now].l;
else
{
rank-=fhq[fhq[now].l].size+1;//在右子树的排名为[当前排名 - (左子树大小+1)]
now=fhq[now].r;
}
}
printf("%d\n",fhq[now].val);
}
/*
找前驱(比当前数小的最大的数):
按照val-1分裂成树x和树y
树x中最右边的数为最大值
*/
inline void pre(int val)
{
split(root,val-1,x,y);
int now=x;
while(fhq[now].r)
now=fhq[now].r;
printf("%d\n",fhq[now].val);
root=merge(x,y);
}
/*
找后继(比当前数大的最小的数):
按照val分裂成树x和树y
树y中最左边的数为最小值
*/
inline void nxt(int val)
{
split(root,val,x,y);
int now=y;
while(fhq[now].l)
now=fhq[now].l;
printf("%d\n",fhq[now].val);
root=merge(x,y);
}
int n;
int main()
{
scanf("%d",&n);
while(n--)
{
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1)
ins(x);
else if(opt==2)
del(x);
else if(opt==3)
get_rank(x);
else if(opt==4)
get_num(x);
else if(opt==5)
pre(x);
else if(opt==6)
nxt(x);
}
return 0;
}（先等我看懂）
你说的对，但是文艺平衡树我还是不知道要怎么说所以先代码上来，让我再看看
#include<iostream>
#include<random>
using namespace std;
const int N=1e5+5;
struct node{
int l,r;
int val,key;
int size;
bool reverse; //翻转懒标记
}fhq[N];
int cnt,root;
mt19937 rnd(210828);
inline int newnode(int val)
{
fhq[++cnt].val=val;
fhq[cnt].key=rnd();
fhq[cnt].size=1;
return cnt;
}
inline void update(int now)
{
fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
inline void pushdown(int now) //下传懒标记
{
swap(fhq[now].l,fhq[now].r);
fhq[fhq[now].l].reverse^=1;
fhq[fhq[now].r].reverse^=1;
fhq[now].reverse=0;
}
//文艺平衡树是按照树的大小分裂
void split(int now,int siz,int &x,int &y)
{
if(!now) x=y=0;
else
{
if(fhq[now].reverse) pushdown(now);
if(fhq[fhq[now].l].size<siz)
{
x=now;
split(fhq[now].r,siz-fhq[fhq[now].l].size-1,fhq[now].r,y);
}
else
{
y=now;
split(fhq[now].l,siz,x,fhq[now].l);
}
update(now);
}
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(fhq[x].key>fhq[y].key)
{
if(fhq[x].reverse) pushdown(x);
fhq[x].r=merge(fhq[x].r,y);
update(x);
return x;
}
else
{
if(fhq[y].reverse) pushdown(y);
fhq[y].l=merge(x,fhq[y].l);
update(y);
return y;
}
}
//反转操作
void reverse(int l,int r)
{
int x,y,z;
split(root,l-1,x,y);
split(y,r-l+1,y,z);
fhq[y].reverse^=1;
root=merge(merge(x,y),z);
}
void ldr(int now)
{
if(!now) return ;
if(fhq[now].reverse) pushdown(now);
ldr(fhq[now].l);
printf("%d ",fhq[now].val);
ldr(fhq[now].r);
}
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
root=merge(root,newnode(i));
while(m--)
{
int l,r;
cin>>l>>r;
reverse(l,r);
}
ldr(root);
return 0;
}（几天集训学的初三下册没时间先丢代码）
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,opt,x;
int root,tot;
struct Splay{
int fa,siz,ch[3],val,cnt;
}t[N];
void maintain(int x){
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt;
}//维护
bool get(int x){
return x==t[t[x].fa].ch[1];
}//判断当前节点是左儿子还是右儿子
void clear(int x){
t[x].ch[0]=t[x].ch[1]=t[x].fa=t[x].val=t[x].siz=t[x].cnt=0;
}//删除当前节点
void rotate(int x){
int y=t[x].fa,z=t[y].fa,lor=get(x);
t[y].ch[lor]=t[x].ch[lor^1];
if(t[x].ch[lor^1]) t[t[x].ch[lor^1]].fa=y;
t[x].ch[lor^1]=y;
t[y].fa=x;
t[x].fa=z;
if(z) t[z].ch[y==t[z].ch[1]]=x;
maintain(y),maintain(x);
}//旋转x节点，好麻烦啊自己看自己推一下吧
//使用次数最多的 Splay 树的主要函数
void splay(int x){
while(t[x].fa){
int f=t[x].fa;
if(t[f].fa) rotate(get(x)==get(f)?f:x);
rotate(x);
}//如果在同一条直链上就先旋转父亲节点，否则就直接旋转当前节点
root=x;
}//将x旋转为根节点，每次操作或者询问完都要把操作过的放到树根
void ins(int x){
if(!root){
t[++tot].val=x;
t[tot].cnt++;
root=tot;
maintain(root);
return ;
}//没有树根那就放进去呗~
int now=root,f=0;
while(1){
if(t[now].val==x)
{
t[now].cnt++;
maintain(now);
splay(now);//必然操作捏~
break;
}//如果当前节点是要插入的数
f=now;
now=t[now].ch[t[now].val<x];//val>k就是1在右字数，反之左子树
if(!now){
t[++tot].val=x;
t[tot].cnt++;
t[tot].fa=f;
t[f].ch[t[f].val<x]=tot;
maintain(tot);
splay(tot);//必然操作捏~
break;
}//找不到值为x的点就插入
}
}
int get_rank(int x){
int rank=0,now=root;
while(1)
{
if(x<t[now].val){
now=t[now].ch[0];
}
else{
rank+=t[t[now].ch[0]].siz;
if(x==t[now].val){
splay(now);//必然操作捏~
return rank+1;
}
rank+=t[now].cnt;
now=t[now].ch[1];
}
}
}
int get_num(int rank){
int now=root;
while(1){
if(t[now].ch[0]&&t[t[now].ch[0]].siz>=rank){
now=t[now].ch[0];
}
else{
rank-=t[now].cnt+t[t[now].ch[0]].siz;
if(rank<=0){
splay(now);//就是必然操作捏！~
return t[now].val;
}
now=t[now].ch[1];
}
}
}
int pre(){
int now=t[root].ch[0];
if(!now) return now;
while(t[now].ch[1]) now=t[now].ch[1];
splay(now);//拉到根上
return now;
}//前驱是左子树中最右边的节点
int nxt(){
int now=t[root].ch[1];
if(!now) return now;
while(t[now].ch[0]) now=t[now].ch[0];
splay(now);//拉到根上
return now;
}//后继是右字数中最左边的节点
void del(int x){
get_rank(x);//将要修改的数放到根节点
if(t[root].cnt>1){
t[root].cnt--;
maintain(root);
return ;
}//要删除的节点有多个那么就把其中一个删去
if(!t[root].ch[0]&&!t[root].ch[1]){
clear(root);
root=0;
return ;
}//只有一个根节点时就直接删去
if(!t[root].ch[0]){
int now=root;
root=t[root].ch[1];
t[root].fa=0;
clear(now);
return ;
}//哭了没有左儿子，那么就把右儿子拉上来
if(!t[root].ch[1]){
int now=root;
root=t[root].ch[0];
t[root].fa=0;
clear(now);
return ;
}//哭了没有右儿子，那么就把左儿子拉上来
//太棒了如果有两个儿子的话就合并
int now=root;
int p=pre();//找前驱
t[t[now].ch[1]].fa=p;//右子树的 baba 就是 p 啦~
t[p].ch[1]=t[now].ch[1];//x 的儿子就是右子树啦~
clear(now);//删掉咯~
maintain(root);//因为前边是要找前驱所以现在 p 才是根啦~
}
int main()
{
cin>>n;
while(n--)
{
cin>>opt>>x;
if(opt==1)
ins(x);
else if(opt==2)
del(x);
else if(opt==3)//这里错了划重点
ins(x),cout<<get_rank(x)<<endl,del(x);
else if(opt==4)
cout<<get_num(x)<<endl;
else if(opt==5)//查找前驱后继都不太一样
ins(x),cout<<t[pre()].val<<endl,del(x);
else
ins(x),cout<<t[nxt()].val<<endl,del(x);
}
return 0;
}