社区讨论
难道我的splay写成了spaly?
P2286[HNOI2004] 宠物收养场参与者 8已保存回复 21
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 21 条
- 当前快照
- 1 份
- 快照标识符
- @mi7ytg7s
- 此快照首次捕获于
- 2025/11/21 05:50 4 个月前
- 此快照最后确认于
- 2025/11/21 06:52 4 个月前
照理来讲此题用splay应该跑得非常迅速qwq
但是我丑陋的splay却必须吸一口氧才能活下来
所以为啥呢qwq,请大佬调一下错吧,splay代码已经封装好放在下面了
Cstruct splay_balanceBST
{
vector<int> bin;
int root,son[N][2],siz[N],fa[N],val[N],cnt[N],tl;
inline int chk(int tmp)
{
return son[fa[tmp]][1]==tmp;
}
inline void up(int tmp)
{
siz[tmp]=siz[son[tmp][0]]+siz[son[tmp][1]]+cnt[tmp];
}
inline void rotate(int tmp)
{
int f=fa[tmp],grf=fa[f];
int p=chk(tmp),q=p^1;
son[f][p]=son[tmp][q],fa[son[tmp][q]]=f;
son[grf][chk(f)]=tmp,fa[tmp]=grf;
son[tmp][q]=f,fa[f]=tmp;
up(f),up(tmp);
}
inline void splay(int tmp,int aim)
{
while(fa[tmp]!=aim)
{
int f=fa[tmp],grf=fa[f];
if(grf!=aim&&chk(tmp)==chk(f)) rotate(f);
else rotate(tmp);
}
if(!aim) root=tmp;
}
inline void tort(int tmp)
{
int cur=root;
while(son[cur][tmp>val[cur]] && tmp!=val[cur]) cur=son[cur][tmp>val[cur]];
splay(cur,0);
}
inline void ins(int tmp)
{
int cur=root,fnp=0;
while(cur && tmp!=val[cur]) fnp=cur,cur=son[cur][tmp>val[cur]];
if(cur) siz[cur]++,cnt[cur]++;
else
{
if(bin.empty()) cur=++tl;
else cur=bin[bin.size()-1],bin.pop_back();
if(fnp) son[fnp][tmp>val[fnp]]=cur;
val[cur]=tmp;
fa[cur]=fnp,siz[cur]=1,cnt[cur]=1;
son[cur][0]=son[cur][1]=0;
}
splay(cur,0);
}
inline int prepos(int tmp)
{
tort(tmp);
if(val[root]<tmp) return root;
int cur=son[root][0];
while(son[cur][1]) cur=son[cur][1];
splay(cur,0);
return cur;
}
inline int succpos(int tmp)
{
tort(tmp);
if(val[root]>tmp) return root;
int cur=son[root][1];
while(son[cur][0]) cur=son[cur][0];
splay(cur,0);
return cur;
}
inline void del(int tmp)
{
int pr=prepos(tmp),suc=succpos(tmp);
splay(pr,0),splay(suc,root);
int aim=son[suc][0];
if(!aim) return;
else if(cnt[aim]==1)
{
bin.push_back(aim);
son[suc][0]=0;
}
else
{
cnt[aim]--,siz[aim]--;
splay(aim,0);
}
}
} pet,peo;
回复
共 21 条回复,欢迎继续交流。
正在加载回复...