hannibal_Iecter

平衡树

ac自动机(7) bitset(2) BSGS(1) dfs(3) DP(19) ODT(1) splay(1) ST表(2) tarjan(2) 中途相遇法(1) 主席树(4) 二分图(1) 二叉树(1) 分块(1) 分治(3) 回文树(1) 多校(1) 字符串(1) 容斥(2) 并查集(1) 快速乘(1) 数学(9) 整体二分(1) 树链剖分(2) 模拟退火(2) 水题(1) 爬山算法(1) 矩阵快速幂(2) 线性基(1) 线段树(10) 编译器(2) 背包(2) 莫队(1) 计算几何(1) 随机数(1) 高精度(1)

/ 注册

全部文章 / 平衡树（共5篇）

ZJOI2006书架【无旋treap】

这道题相对于普通无旋treap需要多维护一个父亲节点，因为需要找书本编号为S的位置，知道位置就好办了。。 bool isright(int rt) { return tr[tr[rt].fa].ch[1] == rt; } int find(int x) {//如果是右节点，那...

2019-07-15

0 465

loj持久化序列【无旋treap】

//无旋treap真滴nb。。基于spilt和merge两个函数可以做很多事情。。之前有一道模板题基于那道题多了版本更新操作，思路和主席树的思路类似，只新建插入或删除的那条链上的点，其他的点参照之前的版本。然后就没有然后了。。 1.因为要复制一些节点的信息，把节点的数据用结构体存起来比较好写。...

2019-07-14

0 393

洛谷P3391【无旋treap】

什么叫tnd的优雅？这tnd的就是优雅！普通的treap如果遇到区间序列问题就没办法了比如这道splay的模板题，根本没法做。但是总会有神仙让他可以做！我们现在不需要insert和del了，因为都是针对单点维护的操作。我们要学会区间insert和区间del！ split（int...

2019-07-12

0 389

普通平衡树【模板】【treap】

学了一下treap的模板感觉还算容易理解。其实就是平衡二叉树+堆每个节点都有一个随机的权值。根据堆的特性，只有右旋和左旋操作。个人觉得关键代码就插入和删除部分涉及旋转的维护代码需要理解一下，其他的询问操作都很好写。 #pragma GCC optimize(2) #include <...

2019-07-12

0 548

bzoj3173【树状数组】【平衡树】

树状数组解法个人遇到的问题：虽然知道这种问题首先要倒着处理出依次的真实位置。但是想法错了。。我认为是倒着处理每个位置的真实位置为：插入的位置+当前位置之后插入位置比当前插入的位置小的数量结果一直wa 后来找到了一组样例 6 0 1 2 0 3 4 用上面的方法位置结果实际上是错的。是因为当某...

2019-07-11

0 351