给学Splay萌新的一点建议

P3391 【模板】文艺平衡树

zl_just @ 2019-10-12 22:43:43

很早之前就学会了Splay的板子(lrj的指针版,局限性很大),这东西学起来简单,自己一写就挂,这里该大家一点我写板子时遇到的坑,希望对大家有帮助 调了我三个多中午 qwq

$2.$一定要注意不能混淆`0`和`1`,手残的话很难发现这些不明显的错误 $3.$~~多思考,别凭感觉~~,像窝几乎把`identify`,`pushdown`,`rotate`,`kth`,全写错了 qwq ~~自认为码风不错~~,供大家参考 ```cpp #include <cstdio> #include <algorithm> #define In inline using namespace std; template<typename T> In T read(T &res) { int c; for(;(res=getchar()-'0')&&(res<0||res>9);); for(;(c=getchar())&&c>='0'&&c<='9';res=(res<<1)+(res<<3)+c-'0'); return res; } const int maxn = 100000 + 5; int v[maxn],sz[maxn],fa[maxn],filp[maxn]; int ch[maxn][2]; In int identify(int x) { return ch[fa[x]][1]==x; } //是父亲的儿子,而非儿子的父亲,我第一次居然写错了 qwq In int cmp(int x,int k) { return (sz[ch[x][0]]+1==k)?-1:(sz[ch[x][0]]+1<k); } //比较排名,别把自己忘了以及小于号搞反 In void maintain(int x) { sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]]; fa[ch[x][0]]=ch[x][0]?x:0; fa[ch[x][1]]=ch[x][1]?x:0; //维护子节点的父亲 } In void pushdown(int x) { if(!filp[x]) return ; filp[x]=0; swap(ch[x][0],ch[x][1]); ch[x][0]?(filp[ch[x][0]]^=1):0; ch[x][1]?(filp[ch[x][1]]^=1):0; //别把0,1写错 } //类似线段树的建树 int build(int L,int R) { if(L>R) return 0; int mid=(L+R)>>1; ch[mid][0]=build(L,mid-1); ch[mid][1]=build(mid+1,R); maintain(mid); return v[mid]=mid; } //旋转要谨慎 In void rotate(int x) { int fx=fa[x],gf=fa[fx],d=identify(x),d2=identify(fx); ch[fx][d]=ch[x][d^1],ch[x][d^1]=fx; maintain(fx),maintain(x); if((fa[x]=gf)) ch[gf][d2]=x; //特判祖父是不是不存在 } In int splay(int x,int y) { for(int fx,fy=fa[y];(fx=fa[x])!=fy;rotate(x)) if(fa[fx]!=fy) (identify(x)==identify(fx))?rotate(fx):rotate(x); //分别对应一字和之字 return x; } //将x中排名位k的提到x所在的位置 int kth(int x,int k) { int d,y=x; while(x) { pushdown(x); //pushdown只需在这儿就可以了,splay以及rotate中并不需要,因为这时标记已经下传了 d=cmp(x,k); if(d==-1) return splay(x,y); if(d) k-=sz[ch[x][0]]+1; x=ch[x][d]; } return 0; } void print(int x) { pushdown(x); //打印时也需要,别忘了 if(ch[x][0]) print(ch[x][0]); if(v[x]>1) printf("%d ",v[x]-1); if(ch[x][1]) print(ch[x][1]); } int main() { register int l,r,n,m,x,y,root; read(n),read(m); root=build(1,n+1); //将1看作哨兵,打印时全体减一,无需分裂时特判 while(m--) { read(l),read(r); x=kth(root,r+1); y=ch[x][1],fa[y]=ch[x][1]=0; maintain(x); //分裂成1~r+1,r+2~n+1两棵树,实际对应0~r,r+1~n x=kth(x,l),filp[ch[x][1]]^=1; //无需分裂,只要将排名l(实际为l-1)的节点提至树根并给其右子树打标记 root=kth(x,sz[x]),ch[root][1]=y; maintain(root); //合并,maintain完成了维护y父节点的任务 } print(root); return 0; } ``` 希望你能写出自己码风的$Splay

(发题解可能会沉,所以发讨论区了,希望对萌新有帮助)


by Mirasycle @ 2022-05-06 12:37:42

为什么lrj指针版局限大


上一页 |