【code】Splay 模板

#include 
using namespace std;
const int INF = 0x3f3f3f3f;// Splay
class Splay{#define root T[0].son[1]  //T[0]为超级根，树根为超级根的右孩子private:struct Tree{  //一个节点只存储一个数值，一个数值只由一个点存储int fa, son[2]/*0 左，1 右*/, v/*当前节点数值*/, sum/*以当前节点为根的树中所有数值的数量*/, recy/*当前点的数值的数量*/;}T[100005];int ctp/*数值数量*/, ctn/*节点编号*/;void update(int k){  //更新sumT[k].sum = T[T[k].son[1]].sum+T[T[k].son[0]].sum+T[k].recy;}int identify(int k){  //识别自己是左（右）孩子return T[T[k].fa].son[0]==k?0:1;}void connect(int s, int f, int lr){  //建立两点间父子关系T[s].fa = f, T[f].son[lr] = s;}void rotate(int k){  //左（右）旋操作int p = T[k].fa, q = T[p].fa;int lrk = identify(k), lrp = identify(p);int b = T[k].son[lrk^1];connect(b, p, lrk), connect(p, k, lrk^1), connect(k, q, lrp);update(p), update(k);}void splay(int k, int to){  //核心 将点 k 旋转到点 toto = T[to].fa; int up;while(T[k].fa != to){up = T[k].fa;if(T[up].fa == to) rotate(k);else{identify(k)==identify(up)?rotate(up):rotate(k);rotate(k);}}}int creat(int v, int fa){  //新建点T[++ctn].fa = fa, T[ctn].v = v;T[ctn].sum = T[ctn].recy = 1;return ctn;}void destory(int k){  //摧毁点T[k].fa = T[k].sum = T[k].son[1] = T[k].son[0] = T[k].recy = 0;}int find(int v){  //查找点int k = root, next;while(T[k].v != v){next = v 1){T[k].recy--;T[k].sum--;return;}if(!T[k].son[0]) connect(T[k].son[1], 0, 1);else if(!T[k].son[1]) connect(T[k].son[0], 0, 1);else{int ls = T[k].son[0];while(T[ls].son[1]) ls = T[ls].son[1];splay(ls, T[k].son[0]);int rs = T[k].son[1];connect(rs, ls, 1), connect(ls, 0, 1);update(ls);}destory(k);}int rank(int v){  //查询数值 v 的排名int k = root, ans = 0;if(!root) return 0;while(T[k].v != v){if(v < T[k].v) k = T[k].son[0];else{ans += T[T[k].son[0]].sum+T[k].recy;k = T[k].son[1];}if(!k) return 0;}ans += T[T[k].son[0]].sum+1;splay(k, root);return ans;}int atrank(int x){  //查询排名为 x 的数值if(x > ctp) return -INF;int k = root, p;while(1){p = T[T[k].son[0]].sum+T[k].recy;if(x>T[T[k].son[0]].sum && x<=p) break;if(x < p) k = T[k].son[0];else{x -= p;k = T[k].son[1];} }splay(k, root);return T[k].v;}int upper(int v){  //查询数值 v 的后继int k = root, ans = INF;while(k){if(T[k].v>v && T[k].vans) ans = T[k].v;if(v > T[k].v) k = T[k].son[1];else k = T[k].son[0];}return ans;}#undef root
}W;// main
int main(){int n, a, b;scanf("%d", &n);while(n--){scanf("%d%d", &a, &b);if(a == 1) W.push(b);else if(a == 2) W.pop(b);else if(a == 3) printf("%d\n", W.rank(b));else if(a == 4) printf("%d\n", W.atrank(b));else if(a == 5) printf("%d\n", W.lower(b));else printf("%d\n", W.upper(b));}return 0;
}

转载于:https://www.cnblogs.com/bosswnx/p/10570787.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！