本弱菜还不会$fhq-treap$,某场教做人被教做人,于是补之。
题意
给定一个序列,要求你资辞以下操作
- 插入、删除某数
- 区间翻转
- 查询一个数的排名
- 查排名为某个值的数
- 求前驱后继
- 区间翻转
- 区间右移(整体右移,并且区间终点的数变为区间起点)
然后就有了$fhq-treap$
操作
$treap$每个节点有个权值,权值保持二叉搜索树结构;每个节点有个优先级,优先级保持最小堆结构。
合并两个子树
按照优先级大小合并即可,并返回合并后树的根节点。1234567891011121314int merge(int x,int y){ if(!x || !y) return x+y; pushdown(x),pushdown(y); if(prio[x]<prio[y]){ ch[y][0]=merge(x,ch[y][0]); pushup(y); return y; }else{ ch[x][1]=merge(ch[x][1],y); pushup(x); return x; }}
分裂成两个子树
按照特定的权值大小分裂为两个子树或者按照特定的子树大小分裂为两个子树,返回分裂后的两个子树的结点。
按权值
|
|
按大小
|
|
其中$pushdown$是下传区间翻转的标记,需要时加上即可。
插入/删除一个结点
插入
|
|
删除
|
|
前驱/后继
前驱
|
|
后继
|
|
区间翻转
|
|
打印
|
|
排名第k大的数
|
|
查询一个值的排名
|
|
区间整体右移
|
|
模板
普通平衡树
|
|
文艺平衡树
|
|
863D Yet Another Array Queries Problem
|
|