BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash 字符串 数据结构

BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash

题意就是给出字符串,动态插入、修改字符。我们需要数据结构,动态维护序列的哈希值。 $$H(l,r)=\sum _{i=l} ^{r} S[i]*base^{i-l}$$ 考虑这个计算一段字符串hash值的公式,可以通过维护子树hash值,再利用Treap的分裂合并操作动态维护,最后二分答案就好啦。 ···
COGS2421 [HZOI 2016]简单的Treap 笛卡尔树 数据结构

COGS2421 [HZOI 2016]简单的Treap 笛卡尔树

笛卡尔树和Treap一样,维护平衡树和堆性质。当一个序列按照值(自身权值)有序有序时,按照序列相对位置建树即可得到二叉搜索树,同时,赋予其随机的优先级又可以维护其堆性质。 笛卡尔树的构造 设节点权值为v,优先级为r。这里对于 r 而言,我们构造小根堆。 我们将一个节点表示为:(v, r)。首先将所有···
TYVJ1730 二逼平衡树 线段树+Treap 数据结构

TYVJ1730 二逼平衡树 线段树+Treap

树套树第一题!一共搞了仨小时= = 先调好一个正常的Treap,可以封装一下,再去搞嵌套,这样会很好调试。 对[1,n]建立线段树,每个节点对应一颗Treap,初始时,在线段树中,将区间中的每个点都插入对应的Treap 查询区间排名:线段树分解,查询区间中比该数小的有多少。 查询区间K小:二分答案,···