学习了一下splay。
splay主要就是干线段树干的活，外加区间翻转，插入删除，还有分裂合并。
建树 就是普通的建成二叉树，为了方便以后的区间操作，会在两边建两个辅助的点。
int build(int l,int r,int y) // [l,r],父亲是y { if(l > r) return 0; int mid = (l + r) / 2; int x = insert(a[mid]); f[x] = y; //建当前节点，insert是插入节点函数 if(l == r) return x; tt[x][0] = build(l,mid - 1,x); tt[x][1] = build(mid + 1,r,x); pushup(x);//和线段树一样吧 return x; }insert 函数
int insert(int key){ int o; if(shan[0] > 0) o = shan[shan[0]--]; else o = tot++; //因为splay有删除操作，所以要建一个栈（shan）来收容以前删除的点，重复利用 ... //这里视题目而定，对点进行初始化 return 0; }splay 和 treap的不同主要是splay一般是把要操作的区间旋上去进行操作。而treap则给每个点加修正值，维护成堆的结构，来保证复杂度。所以splay最核心的就是splay操作了呗。
介绍splay操作就得先介绍rotate，旋转操作，和普通的平衡二叉树的旋转没有区别。
int son(int x){ if(tt[f[x]][0] == x) return 0;else return 1; //这个函数用来判断x是父亲的哪个儿子 } void rotate(int x){ int y = f[x],z = son(x); //三步走 tt[y][z] = tt[x][1 - z]; if(tt[x][1 - z]) f[tt[x][1 - z]] = y; //先是把x的儿子接到y上 f[x] = f[y]; if(f[y]) tt[f[y]][son(y)] = x; //把x接到y的父亲上 f[y] = x; tt[x][1 - z] = y; //y接到x上 pushup(y),pushup(x);//转完要维护信息 return； } void splay(int x,int y){//把x旋到y的子树上面去 if(x == y) return; update(x,y);//由于x要旋转上去，所以要先把标记理一理 while(f[x] != y){ if(f[f[x]] != y){ if(son(f[x]) == son(x)) rotate(f[x]); else rotate(x);//和普通avl树的旋转一样 } rotate(x); } if(y == 0) root = x; }pushup和pushdown函数和线段树的并无二致。
del函数
void del(int x){ if(x == 0) return;//空树不删了 shan[++shan[0]] = x; del(tt[x][0]);del(tt[x][1]); }update函数
void update(int x,int y){ do{ d[++d[0]] = x; x = f[x]; }while(x != y); while(d[0]) pushdown(x); }//因为要从上往下pushdown，所以要用栈从下往上存起来对区间[l,r]进行操作，先把l - 1旋到根节点，再把r + 1旋到l - 1的右儿子，那么[l,r]在r + 1的左儿子，该打标记打标记，该删删，该加加。
int x = kth(root,l - 1);splay(x,0); int y = kth(root,r + 1);splay(y,x); //balabala操作其中kth操作就是二叉树找第k个节点。
分裂和合并 有的时候让把哪一段取出来放到前面还是后面，就要分裂和合并。
void split(int root,int k,int &l,int &r){ int x = kth(root,k);splay(x,0); l = x; r = tt[x][1]; f[r] = 0; tt[x][1] = 0;update(l); return; } void merge(int root1,int root2,int & newroot){ int x = kth(root1,size[root1]); splay(x,0); t[x][1] = root2; f[root2] = x; update(root1); newroot = root1; }例题就是bzoj1500
