Fhq-Treap 模板
2022/8/2 6:23:54
本文主要是介绍Fhq-Treap 模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
namespace Fhq_Treap { int ch[N][3], siz[N], val[N], cnt, rnd[N]; inline void update(int x); inline int newnode(int x); inline int Kth(int now, int k); inline void split(int now, int k, int &x, int &y); inline int merge(int A, int B); inline void insert(int a); inline void Delete(int a); inline int find_rank(int a); inline int find_Kth(int a); inline int find_pre(int a); inline int find_nxt(int a); } namespace Fhq_Treap { inline void update(int x) { siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]]; } inline int newnode(int x) { val[++cnt] = x; siz[cnt] = 1; rnd[cnt] = rand(); return cnt; } inline int Kth(int now, int k) { while (1) { if (k <= siz[ch[now][0]])now = ch[now][0]; else if (k == siz[ch[now][0]] + 1)return now; else k -= siz[ch[now][0]] + 1, now = ch[now][1]; } } inline void split(int now, int k, int &x, int &y) { if (now == 0) { x = y = 0; return ; } if (val[now] <= k) { x = now; split(ch[now][1], k, ch[now][1], y); } else { y = now; split(ch[now][0], k, x, ch[now][0]); } update(now); } inline int merge(int A, int B) { if (!A || !B)return A + B; else if (rnd[A] < rnd[B]) { ch[A][1] = merge(ch[A][1], B); update(A); return A; } else { ch[B][0] = merge(A, ch[B][0]); update(B); return B; } } inline void insert(int a) { split(root, a, x, y); root = merge(merge(x, newnode(a)), y); } inline void Delete(int a) { split(root, a, x, z); split(x, a - 1, x, y); y = merge(ch[y][0], ch[y][1]); root = merge(merge(x, y), z); } inline int find_rank(int a) { split(root, a - 1, x, y); int ret = siz[x] + 1; root = merge(x, y); return ret; } inline int find_Kth(int a) { return val[Kth(root, a)]; } inline int find_pre(int a) { split(root, a - 1, x, y); int ret = val[Kth(x, siz[x])]; root = merge(x, y); return ret; } inline int find_nxt(int a) { split(root, a, x, y); int ret = val[Kth(y, 1)]; root = merge(x, y); return ret; } }
这篇关于Fhq-Treap 模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!