ToB企服应用市场:ToB评测及商务社交产业平台

标题: 随用随取的平衡树板子！ [打印本页]

---

作者: 涛声依旧在    时间: 2024-8-13 15:27
标题: 随用随取的平衡树板子！
如今已实现无旋Treap和Splay。
利用阐明及注意事项：

• 利用命名空间+结构体进行封装，利用时只需jser::Treap或using namespace jser即可。例如：
  

1. /*
2. way 1
3. */
4. using namespace jser;
5. Treap tree;
6. /*
7. way 2
8. */
9. jser::Splay tree;

复制代码

• Treap随机数生成采用random_device和mt19937，在某些评测姬上可能不适用，可以换用rand（注意数据范围）或手写随机数生成器。
  
• 利用数据范围宏定义，在结构体开头有数组大小N的宏定义，方便大家修改数据范围。
  
• 多处利用register，C++17及以上不适用，记得更换。
  
• 存储数值为int类，注意是否需要开long long。
  

功能介绍

• void push(int x)加入一个 \(x\) 值。
  
• void pop(int x)删除一个 \(x\) 值。
  
• int rank(int x)返回 \(x\) 在数列里的排名。
  
• int kth(int x)返回在数列中排名为 \(x\) 的数值。
  
• int pre(int x)返回数值 \(x\) 在数列中的前驱。如果没有，返回负无穷。
  
• int next(int x)返回数值 \(x\) 在数列中的后继。如果没有，返回正无穷。
  

代码时候

教授の全局宏定义（不喜可换）：

1. #define il inline
2. #define ri register int
3. #define inf 0x3f3f3f3f

复制代码

正片：
[code]namespace jser{        random_device rd;        long long sed=rd();        mt19937 rad(time((time_t*)&sed));        il long long getrand(long long x,long long y)        {                return rad()%(y-x+1)+x;        }        struct Treap        {                #define N 200002                int root,cnt;                int val[N],siz[N],pri[N],lson[N],rson[N];                il void pushup(int x)                {                        siz[x]=siz[lson[x]]+siz[rson[x]]+1;                }                il int merge(int x,int y)                {                        if(!x||!y)                        {                                return x|y;                        }                        if(pri[x]

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4