可持久化数据结构+树套树 专题训练 数据结构

可持久化数据结构+树套树 专题训练

联赛后最早刷的两个专题知识点,主要是通过比较麻烦的数据结构来提升代码能力。 基本上是按照做题的顺序来写的。 可持久化数据结构 bzoj 3123 [Sdoi2013]森林 给出一片森林,每个点有点权,要求支持动态连边操作,同时查询路径k小值,强制在线。 之前暑假做过弱化版,这道题就是动态维护倍增LC···
BZOJ4553 [Tjoi2016&Heoi2016]序列 树套树+三维偏序 数据结构

BZOJ4553 [Tjoi2016&Heoi2016]序列 树套树+三维偏序

刚开始做的时候没好好地当作三维偏序来做,只是乱搞,后来膜了CDQ的思路,大概有了点套路,于是决定用树状数组套无旋treap来搞这道题(其实是因为还没打过CDQ呵呵)。 按照最长不降子序列的DP做法,DP方程显然为F[i]=max{f[j]}+1。问题转为了如何寻找最优的转移点j。 首先,按照套路,先···
TYVJ1730 二逼平衡树 线段树+Treap 数据结构

TYVJ1730 二逼平衡树 线段树+Treap

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