- 浏览: 118389 次
- 性别:
- 来自: 北京
-
最新评论
// Treap // Tested: bjtu1057, hdu1004, pku1002 typedef int KEY; typedef int VALUE; struct node_t { int ch[2], pr; KEY key; VALUE value; } T[maxn]; int size; // init: size = 0 int new_node() { T[size].ch[0] = T[size].ch[1] = -1, T[size].pr = rand(); return size++; } struct treap_t { int root; // init: root = -1 void clear() { root = -1; } void adjust(int &p, int k) { int x = T[p].ch[k]; T[p].ch[k] = T[x].ch[1 - k], T[x].ch[1 - k] = p, p = x; } void insert(int &p, const KEY &key, const VALUE &value) { if (p == -1) { p = new_node(), T[p].key = key, T[p].value = value; } else if (key == T[p].key) { T[p].value += value; } else { int k = key < T[p].key ? 0 : 1; insert(T[p].ch[k], key, value), adjust(p, k); } } void erase(int &p, const KEY &key) { if (p == -1) return; if (key == T[p].key) { int L = T[p].ch[0], R = T[p].ch[1], k = L != -1 ? 0 : -1; if (R != -1 && (k == -1 || T[R].pr < T[L].pr)) k = 1; if (k == -1) p = -1; else adjust(p, k), T[p].ch[1 - k] = -1; } else { int k = key < T[p].key ? 0 : 1; erase(T[p].ch[k], key); } } int find(int p, const KEY &key) { if (p == -1 || key == T[p].key) return p; int k = key < T[p].key ? 0 : 1; return find(T[p].ch[k], key); } int lower_bound(int p, const KEY &key) { if (p == -1 || key == T[p].key) return p; int k = key < T[p].key ? 0 : 1; if (T[p].ch[k] == -1) return k == 1 ? -1 : p; return lower_bound(T[p].ch[k], key); } int upper_bound(int p, const KEY &key) { int x = lower_bound(p, key); if (x == -1 || key < T[x].key) return x; return T[x].ch[1]; } } treap;
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1151/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 839线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 849线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 887写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 970转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1188封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 797终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 602写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1137源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 803import java.util.*; import j ... -
整数划分
2010-10-07 10:38 839#include <cstdio> #inc ... -
矩阵快速幂
2010-09-18 14:24 1050typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1134最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1291Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 774static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 877标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 848“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1039“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1004推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ... -
RMQ模板
2010-07-28 11:04 1185/* * Author: rush * Creat ...
相关推荐
treap是一种小巧轻便的数据结构,特别适合信息学竞赛。 本文讲解treap的分析与应用,适于初学者学习,
treap的基本操作,例如插入删除,以及它的代码实现!
基本Treap.ppt
平衡树treap的思想
treap 的可视化实现,可以对树堆节点进行动态的添加和删除
Treap数据结构和Skip Lists,英文附图解,若侵犯版权,我立即删掉
Treap树算法,目前实现了节点插入,为算法导论上的算法
详细介绍了Treap的各种操作,以及它与Splay的比较,尤其适合已有Splay基础并想进一步学习Treap的同学。
郭家宝的平衡树讲稿 很全很详细。 ~!!!!!!!!
指针构建非旋treap,代替线段树,可支持持久化,luogu3372可过.
treap树算法实现,VB编写的代码,含可视化操作界面
avl树,bst树(二叉查找树),rbt(红黑树),sbt(size平衡树),splay(伸展树),treap树。 3.代码以一个bst_base为基础,实现通用算法。将对象特征和存储结构通过模板参数向上传递,实现特化算法。最终各个不同...
void Insert(Node * &o,int x){//0为左子树,1为右子树 if(o==NULL){o = new Node(); o->ch[0]=o->ch[1]=NULL;o->key=x;o->weight=rand();} else{ int d=o->cmp(x); Insert(o->ch[d],x);...if(o->ch[d]->weight>o->...
Treap原理和实现方法.pdf
http://ybt.ssoier.cn:8088 信息学奥赛一本通(提高篇)测试数据\第4部分 数据结构(提高篇)\ 第6章 平衡树Treap 测试数据
python库。 资源全名:treap-1.31.tar.gz
FHQ无旋Treap(按值分裂)的简单学习-自己记录用的
史上最简单的平衡树——无旋Treap.pdf
无旋Treap(按树的大小分裂)的简单学习-自己记录用的
主要介绍了数据结构之Treap详解,本文讲解了Treap的基本知识、Treap的基本操作、Treap的高级操作技巧等,需要的朋友可以参考下