安徽万振建设集团网站,优良的网站邮箱服务器提供商isp,卫浴网站模板,网址提交入口大全打LCT的时候发现Splay很不熟, 因此这里贴一下模板 洛谷P3369 https://www.luogu.org/problem/show?pid3369#sub /*
提一些要注意的点:
1. 注意判断边界, 不要访问到空节点
2. 每一次操作或访问完以后, 记得要splay到root
3. insert操作只要update当前节点和父亲节点即可, 因为… 打LCT的时候发现Splay很不熟, 因此这里贴一下模板 洛谷P3369 https://www.luogu.org/problem/show?pid3369#sub /*
提一些要注意的点:
1. 注意判断边界, 不要访问到空节点
2. 每一次操作或访问完以后, 记得要splay到root
3. insert操作只要update当前节点和父亲节点即可, 因为还会上旋到root
4.牢记双旋的打法
5. delete时需要把将要delete的点上旋的根, 因此可与find共用函数
6. 在找一个bst中原本不存在的点的前驱或后继时, 可先将该点插入, 然后找前驱或后继, 然后再删除
*/
#includecstdio
#includecctype
#includecstring
using namespace std;
void read(int x)
{x 0;char c;int flag 1;while(! isgraph(c getchar()))if(c -)flag * - 1;while(isgraph(c))x x * 10 c - 0, c getchar();x * flag;
}
const int MAXN (int)1e5;
int top;
struct node
{int key, cnt, ch[2], size, fa;
}T[MAXN 64];
int root;
void create(int x)
{T[top].ch[0] T[top].ch[1] - 1;T[top].key x;T[top].cnt 1;T[top ].size 1;
}
void update(int u)
{T[u].size T[u].cnt;if(T[u].ch[0] ! - 1)T[u].size T[T[u].ch[0]].size;if(T[u].ch[1] ! - 1)T[u].size T[T[u].ch[1]].size;
}
inline int getson(int p)
{return (p T[T[p].fa].ch[1]);
}
void rotate(int p)
{int fa T[p].fa, fafa T[fa].fa, k getson(p);T[fa].ch[k] T[p].ch[k ^ 1];T[T[p].ch[k ^ 1]].fa T[p].fa;T[p].ch[k ^ 1] fa;T[fa].fa p;T[p].fa fafa;if(fafa ! - 1)T[fafa].ch[T[fafa].ch[1] fa] p;update(fa), update(p);
}
void splay(int u)
{for(int fa; (fa T[u].fa) ! - 1; rotate(u))if(T[fa].fa ! - 1)rotate((getson(u) getson(fa)) ? fa : u);root u;
}
void insert(int x)
{if(root ! - 1){int p root, fa - 1;while(1){if(T[p].key x){T[p].cnt ;update(p), update(fa);//这里只需要更新p和fa就可以了 splay(p);//因为这里还会更新到p到根节点上的所有祖先 break;}fa p;p T[p].ch[x T[fa].key];if(p - 1){create(x);T[top - 1].fa fa;T[fa].ch[x T[fa].key] top - 1;update(fa);splay(top - 1);break;}}}elsecreate(x), T[top - 1].fa root, root top - 1;
}
int find(int x) //写得有点奇怪了, 因为强行把两个操作合并在一起233
{int p root, sum 0;while(1){if(x T[p].key)p T[p].ch[0];else{sum (T[p].ch[0] - 1) ? 0 : T[T[p].ch[0]].size;if(x T[p].key){splay(p);return sum 1;}sum T[p].cnt;p T[p].ch[1];}}
}
int get_pre()
{int p T[root].ch[0];while(T[p].ch[1] ! - 1)p T[p].ch[1];return p;
}
void del(int x) //下面就是无聊的分类讨论了
{find(x);if(T[root].cnt 1){T[root].cnt --;update(root);return;}if(T[root].ch[0] - 1 T[root].ch[1] - 1){root - 1;return;}if(T[root].ch[1] - 1){int tmp root;root T[root].ch[0];T[root].fa - 1;return;}elseif(T[root].ch[0] - 1){int tmp root;root T[root].ch[1];T[root].fa - 1;return;}int pre get_pre(), tmp root;splay(pre);T[T[tmp].ch[1]].fa root;T[root].ch[1] T[tmp].ch[1];update(root);
}
void print(int x)
{if(x 0)putchar(-);if(x 0)putchar(0);int ans[10], top 0;while(x)ans[top ] x % 10, x / 10;for(; top; top --)putchar(ans[top - 1] 0);
}
int get_rank(int x)
{int p root;while(1){if(T[p].ch[0] ! - 1 x T[T[p].ch[0]].size)p T[p].ch[0];else{int tmp ((T[p].ch[0] ! - 1) ? T[T[p].ch[0]].size : 0) T[p].cnt;if(x tmp)return T[p].key;x - tmp;p T[p].ch[1]; }}
}
int get_next()
{int p T[root].ch[1];while(T[p].ch[0] ! - 1)p T[p].ch[0];return p;
}
int main()
{#ifndef ONLINE_JUDGEfreopen(L3369.in, r, stdin);freopen(L3369.out, w, stdout);#endifint n;read(n);root - 1;top 0;for(int i 0; i n; i ){int opt, x;read(opt), read(x);switch (opt){case 1: insert(x); break;case 2: del(x); break;case 3: print(find(x)); putchar(\n); break;case 4: print(get_rank(x)); putchar(\n); break;case 5: {insert(x);print(T[get_pre()].key);putchar(\n);del(x);break;}case 6:{insert(x);print(T[get_next()].key);putchar(\n);del(x);break;}}}
} 转载于:https://www.cnblogs.com/ZeonfaiHo/p/6402841.html
