前几天刚刚自学了一下splay，发现思路真简单实现起来好麻烦
先贴一下头文件
# include <stdio.h> # include <stdlib.h> # include <iostream> # include <string.h> # define ll long long # define RG register//卡常 # define IL inline//再卡常 # define UN unsigned # define mem(a, b) memset(a, b, sizeof(a)) # define min(a, b) ((a) < (b)) ? (a) : (b) # define max(a, b) ((a) > (b)) ? (a) : (b) using namespace std; 核心旋转操作 Splay操作（之后的操作基本上都要用到） 1.当旋转的节点为爷爷节点的左儿子的左儿子时 进行两次右旋操作，先转父亲，再转自己 2.当旋转的节点为爷爷节点的左儿子的右儿子时 进行一次左旋操作，一次右旋操作，都转自己 3.如果要转到的点的为爷爷节点的右儿子，直接左旋 4.剩下两种情况把以上两种情况左右互换即可 贴一段代码 IL void Rot(RG tree *x, RG int i){ //0为左旋，1为右旋，0为左儿子，1为右儿子 RG tree *y = x -> fa; y -> ch[!i] = x -> ch[i]; if(x -> ch[i] != NULL) x -> ch[i] -> fa = y; x -> fa = y -> fa; if(y -> fa != NULL) if(y -> fa -> ch[0] == y) y -> fa -> ch[0] = x; else y -> fa -> ch[1] = x; x -> ch[i] = y; y -> fa = x; if(y == root) root = x; } IL void Splay(RG tree *x, RG tree *f){ while(x -> fa != f) if(x -> fa -> fa == f) if(x == x -> fa -> ch[0]) Rot(x, 1); else Rot(x, 0); else{ RG tree *y = x -> fa, *z = y -> fa; if(z -> ch[0] == y) if(y -> ch[0] == x) Rot(y, 1), Rot(x, 1); else Rot(x, 0), Rot(x, 1); else if(y -> ch[1] == x) Rot(y, 0), Rot(x, 0); else Rot(x, 1), Rot(x, 0); } } 插入操作 和二叉排序树一样，只不过弄完后把它Splay到根（不要问为什么） 丑陋的代码 IL void Insert(RG int num){ RG tree *x = root; if(x == NULL){ x = new tree; x -> val = num; root = x; } else while(2333) if(num < x -> val){ if(x -> ch[0] == NULL){ x -> ch[0] = new tree; x -> ch[0] -> fa = x; x = x -> ch[0]; x -> val = num; break; } x = x -> ch[0]; } else if(num > x -> val){ if(x -> ch[1] == NULL){ x -> ch[1] = new tree; x -> ch[1] -> fa = x; x = x -> ch[1]; x -> val = num; break; } x = x -> ch[1]; } Splay(x, NULL); } 查找 与二叉排序树一样 IL void Find(RG int num){ RG tree *x = root; while(x -> val != num) if(num < x -> val) x = x -> ch[0]; else x = x -> ch[1]; Splay(x, NULL); } 查找前驱和后缀 前驱，跳到它的左儿子再不停地跳右儿子 后继，跳到它的右儿子再不停地跳左儿子 IL void Findmx(RG tree *x, RG tree *f, RG int i){ //0表示后继，1表示前驱，f为该节点，x为它的左或右儿子1 while(x -> ch[i] != NULL) x = x -> ch[i]; Splay(x, f); } 删除操作 先找到数字的位置，Splay到根，删掉它，找它左子树中的最大数（前驱）Splay到它下面作为新的根，连接右子树即可 代码 IL void Delete(RG int num){ Find(num); RG tree *x = root; else if(x -> ch[0] == NULL || x -> ch[1] == NULL) if(x -> ch[0] != NULL) root = x -> ch[0], root -> fa = NULL; else if(x -> ch[1] != NULL) root = x -> ch[1], root -> fa = NULL; else root = NULL; else{ Findmx(x -> ch[0], x, 1); root = x -> ch[0]; root -> fa = NULL; root -> ch[1] = x -> ch[1]; if(root -> ch[1] != NULL) root -> ch[1] -> fa = root; } } 查找某数的排名 实行查找操作，排名就是他左子树大小加一 IL int Size(RG tree *x){ return (x == NULL) ? 0 : x -> size + 1; } IL int Rank(RG int num){ Find(num); return Size(root -> ch[0]) + 1; } 查找排名为k的数 若大于当前的左子树大小加一，跳右儿子，k -= 左子树大小加一； 否则跳右节点 IL int Pos(RG int num){ RG tree *x = root; while(2333){ RG int l = Size(x -> ch[0]); if(num == l + 1) break; if(num <= l) x = x -> ch[0]; else{ num -= (l + 1); x = x -> ch[1]; } } return x -> val; }以上就是基本操作
关于更新 如子树大小 IL int Size(RG tree *x){ return (x == NULL) ? 0 : x -> size + 1; } IL void Updata(RG tree *x){ if(x == NULL) return; x -> size = Size(x -> ch[0]) + Size(x -> ch[1]); } IL void Rot(RG tree *x, RG int i){ //0为左旋，1为右旋 RG tree *y = x -> fa; y -> ch[!i] = x -> ch[i]; if(x -> ch[i] != NULL) x -> ch[i] -> fa = y; x -> fa = y -> fa; if(y -> fa != NULL) if(y -> fa -> ch[0] == y) y -> fa -> ch[0] = x; else y -> fa -> ch[1] = x; x -> ch[i] = y; y -> fa = x; Updata(y); //大佬说写在这里 if(y == root) root = x; } IL void Splay(RG tree *x, RG tree *f){ while(x -> fa != f) if(x -> fa -> fa == f) if(x == x -> fa -> ch[0]) Rot(x, 1); else Rot(x, 0); else{ RG tree *y = x -> fa, *z = y -> fa; if(z -> ch[0] == y) if(y -> ch[0] == x) Rot(y, 1), Rot(x, 1); else Rot(x, 0), Rot(x, 1); else if(y -> ch[1] == x) Rot(y, 0), Rot(x, 0); else Rot(x, 1), Rot(x, 0); } Updata(x); //大佬说要写在这里 }简单的栗子： 链接bzoj3224 请读者思考2分钟 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 好了直接看代码 代码调了好久QAQ
# include <stdio.h> # include <stdlib.h> # include <iostream> # include <string.h> # define ll long long # define RG register # define IL inline # define UN unsigned # define mem(a, b) memset(a, b, sizeof(a)) # define min(a, b) ((a) < (b)) ? (a) : (b) # define max(a, b) ((a) > (b)) ? (a) : (b) using namespace std; IL int Get(){ char c = '!'; int z = 1, num = 0; while(c != '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') z = -1, c = getchar(); while(c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar(); return num * z; } struct tree{ tree *fa, *ch[2]; int val, tot, size;//tot用来判断重复的数 IL tree(){ fa = ch[0] = ch[1] = NULL; size = val = tot = 0; } } *root; IL int Size(RG tree *x){ return (x == NULL) ? 0 : x -> size + x -> tot + 1; } IL void Updata(RG tree *x){ if(x == NULL) return; x -> size = Size(x -> ch[0]) + Size(x -> ch[1]); } IL void Rot(RG tree *x, RG int i){ //0为左旋，1为右旋 RG tree *y = x -> fa; y -> ch[!i] = x -> ch[i]; if(x -> ch[i] != NULL) x -> ch[i] -> fa = y; x -> fa = y -> fa; if(y -> fa != NULL) if(y -> fa -> ch[0] == y) y -> fa -> ch[0] = x; else y -> fa -> ch[1] = x; x -> ch[i] = y; y -> fa = x; Updata(y); if(y == root) root = x; } IL void Splay(RG tree *x, RG tree *f){ while(x -> fa != f) if(x -> fa -> fa == f) if(x == x -> fa -> ch[0]) Rot(x, 1); else Rot(x, 0); else{ RG tree *y = x -> fa, *z = y -> fa; if(z -> ch[0] == y) if(y -> ch[0] == x) Rot(y, 1), Rot(x, 1); else Rot(x, 0), Rot(x, 1); else if(y -> ch[1] == x) Rot(y, 0), Rot(x, 0); else Rot(x, 1), Rot(x, 0); } Updata(x); } IL void Insert(RG int num){ RG tree *x = root; if(x == NULL){ x = new tree; x -> val = num; root = x; } else if(num == x -> val) x -> tot++, root = x; else while(2333) if(num < x -> val){ if(x -> ch[0] == NULL){ x -> ch[0] = new tree; x -> ch[0] -> fa = x; x = x -> ch[0]; x -> val = num; break; } x = x -> ch[0]; } else if(num > x -> val){ if(x -> ch[1] == NULL){ x -> ch[1] = new tree; x -> ch[1] -> fa = x; x = x -> ch[1]; x -> val = num; break; } x = x -> ch[1]; } else{ x -> tot++; break; } Splay(x, NULL); } IL void Find(RG int num){ RG tree *x = root; while(x -> val != num) if(num < x -> val) x = x -> ch[0]; else x = x -> ch[1]; Splay(x, NULL); } IL void Findmx(RG tree *x, RG tree *f, RG int i){ while(x -> ch[i] != NULL) x = x -> ch[i]; Splay(x, f); } IL void Delete(RG int num){ Find(num); RG tree *x = root; if(root -> tot) root -> tot--; else if(x -> ch[0] == NULL || x -> ch[1] == NULL) if(x -> ch[0] != NULL) root = x -> ch[0], root -> fa = NULL; else if(x -> ch[1] != NULL) root = x -> ch[1], root -> fa = NULL; else root = NULL; else{ Findmx(x -> ch[0], x, 1); root = x -> ch[0]; root -> fa = NULL; root -> ch[1] = x -> ch[1]; if(root -> ch[1] != NULL) root -> ch[1] -> fa = root; } } IL int Rank(RG int num){ Find(num); return Size(root -> ch[0]) + 1; } IL int Pos(RG int num){ RG tree *x = root; while(2333){ RG int l = Size(x -> ch[0]); if(num > l && num <= l + x -> tot + 1) break; if(num <= l) x = x -> ch[0]; else{ num -= (l + x -> tot + 1); x = x -> ch[1]; } } return x -> val; } int main(){ RG int n = Get(), opt, x; while(n--){ opt = Get(); x = Get(); if(opt == 1) Insert(x); if(opt == 2) Delete(x); if(opt == 3) printf("%d\n", Rank(x)); if(opt == 4) printf("%d\n", Pos(x)); //找前驱后缀：插入数后再删除，显然有更快的（不想打其他方法了，反正能过） if(opt == 5){ Insert(x); Findmx(root -> ch[0], NULL, 1); printf("%d\n", root -> val); Delete(x); } if(opt == 6){ Insert(x); Findmx(root -> ch[1], NULL, 0); printf("%d\n", root -> val); Delete(x); } } return 0; }关于区间操作 一张丑陋的图 把l-1splay到根，r+1splay到根的右儿子，则图中那个丑陋的子树就是要求的[l，r]了。
删除区间 直接断开边（显然浪费空间，自己想办法目前没遇到MLE的情况）
翻转区间 用类似于线段树的懒懒的lazy标记，每次Find，splay等操作时把标记下放，更换两个子树又一个栗子 链接bzoj3223 再思考两分钟 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 看代码
# include <stdio.h> # include <stdlib.h> # include <iostream> # include <string.h> # define ll long long # define RG register # define IL inline # define UN unsigned # define mem(a, b) memset(a, b, sizeof(a)) # define min(a, b) ((a) < (b)) ? (a) : (b) # define max(a, b) ((a) > (b)) ? (a) : (b) using namespace std; IL int Get(){ char c = '!'; int z = 1, num = 0; while(c != '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') z = -1, c = getchar(); while(c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar(); return num * z; } struct tree{ tree *fa, *ch[2]; int size, lazy, pos; IL tree(){ fa = ch[0] = ch[1] = NULL; pos = lazy = size = 0; } IL void Pushdown(){//下放 if(!lazy) return; lazy = 0; if(ch[1] == NULL && ch[0] == NULL) return; if(ch[0] != NULL) ch[0] -> lazy ^= 1; if(ch[1] != NULL) ch[1] -> lazy ^= 1; swap(ch[0], ch[1]); } } *root; int n; IL int Size(RG tree *x){ return (x == NULL) ? 0 : x -> size + 1; } IL void Updata(RG tree *x){ if(x == NULL) return; x -> size = Size(x -> ch[0]) + Size(x -> ch[1]); } IL void Dfs(RG tree *x){ if(x == NULL) return; x -> Pushdown(); Dfs(x -> ch[0]); if(x -> pos && x -> pos <= n) printf("%d ", x -> pos); Dfs(x -> ch[1]); } IL void Rot(RG tree *x, RG int i){ //0为左旋，1为右旋 RG tree *y = x -> fa; x -> Pushdown(); y -> Pushdown(); y -> ch[!i] = x -> ch[i]; if(x -> ch[i] != NULL) x -> ch[i] -> fa = y; x -> fa = y -> fa; if(y -> fa != NULL) if(y -> fa -> ch[0] == y) y -> fa -> ch[0] = x; else y -> fa -> ch[1] = x; x -> ch[i] = y; y -> fa = x; Updata(y); if(y == root) root = x; } IL void Splay(RG tree *x, RG tree *f){ while(x -> fa != f){ x -> Pushdown(); if(x -> fa -> fa == f) if(x == x -> fa -> ch[0]) Rot(x, 1); else Rot(x, 0); else{ RG tree *y = x -> fa, *z = y -> fa; if(z -> ch[0] == y) if(y -> ch[0] == x) Rot(y, 1), Rot(x, 1); else Rot(x, 0), Rot(x, 1); else if(y -> ch[1] == x) Rot(y, 0), Rot(x, 0); else Rot(x, 1), Rot(x, 0); } } Updata(x); } IL tree *Build(RG int l, RG int r, RG tree *f){ RG int mid = (l + r) >> 1; tree *x = new tree; x -> pos = mid; x -> fa = f; if(mid > l) x -> ch[0] = Build(l, mid - 1, x); if(mid < r) x -> ch[1] = Build(mid + 1, r, x); Updata(x); return x; } IL void Find(RG int num, RG tree *f){ RG tree *x = root; while(2333){ x -> Pushdown(); RG int l = Size(x -> ch[0]); if(num < l) x = x -> ch[0]; else if(num == l) break; else{ num -= (l + 1); x = x -> ch[1]; } } Splay(x, f); } IL void Turn(){ RG int l = Get(), r = Get(); Find(l - 1, NULL); Find(r + 1, root); root -> ch[1] -> ch[0] -> lazy ^= 1; } int main(){ n = Get(); RG int m = Get(); root = Build(0, n + 1, NULL); while(m--) Turn(); Dfs(root); printf("\n"); return 0; }解释或代码错误还请大佬指出，本蒟蒻一定会改
