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 disangan233 @ 2019-10-12 23:07:31
@zl_just splay 我倒觉得不如 fhq 常用。。
然后窝现在貌似只会写 fhq 了。。除了写 lct 的时候打个。。
by zl_just @ 2019-10-12 23:09:36
@disangan233 我也是这样认为的,但题解最常用的就是splay,而窝学splay就是为了lct qwq