Category Archives: 树套树

ZOJ 2112 Dynamic Rankings (树状数组套可持久化线段树)

计算区间第k大数,存在动态修改区间某个点的数. 用树状数组套上一个主席树,主席数维护的是区间不同数子的个数,用 …

HDU 5566 Clarke and room (树链剖分,线段树,ac自动机)

给出一棵树,树上每个节点有一个名字字符串,有q个询问,计算树链u-v经过的点对应的字符串是si的子串的最大长度 …

HDU 5412 CRB and Queries (离线,线段树套treap|树状数组套treap)

题意很简单,动态修改某个点的值,然后区间询问第k大数。这题用三种做法乱搞了。 1.线段树套treap,维护ra …

HYSBZ 1146 网络管理Network (树链剖分,数状数组套treap)

题意:对于一棵树,每个节点有权值,动态修改权值并且询问某条链第k大的权值是多少。 题解:这题首先要用树链剖分将 …

BZOJ 3295 动态逆序对 (线段树套treap)

动态删点,求逆序对数.应该是动态删点,所以仅仅线段树无法维护,对于静态情况下用树状数组就可以求出逆序数对了,然 …

ZOJ 2112 Dynamic Rankings (线段树套treap,动态修改区间第k大)

求区间第k大,但是要动态修改,所以要结合treap的第k大和线段树的动态更行。其实线段树套treap就是线段树 …