后缀数组 专题训练 字符串

后缀数组 专题训练

关于后缀数组的学习,还是费了不少精力的,尤其是一开始入门,连个模板都不理解,也不会基数排序,所以这个知识点从六月一直拖到了现在,有两篇专门讲后缀数组的文章,感觉还不错,我就是看了这俩之后才算入了门,转过来: 五分钟搞懂后缀数组!后缀数组解析以及应用(附详解代码) 后缀数组应用小结   之后···
可持久化数据结构+树套树 专题训练 数据结构

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

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

COGS1763(BZOJ2653) middle 主席树+二分

一般的主席树都是建立权值线段树,然后用每个版本划分区间位置,但是这道题就不太一样。首先,考虑要求的是左右端点在一定区间内的中位数,那么这个询问中,左右区间夹着的一段是一定要取的,而左右两端则不定。 考虑在一段区间中,大于等于中位数的数有len/2个,那么,先离散数据,按照区间位置建立主席树,叶子节点···
BZOJ2588 Spoj 10628.Count on a tree 主席树+LCA 数据结构

BZOJ2588 Spoj 10628.Count on a tree 主席树+LCA

要查询树上点对间点权k大,不难想到为每个节点建立权值主席树,每个节点由其父节点的主席树扩展而来,所以只需在DFS时建树即可。查询时二分答案,差分一下,用root[u]+root[v]-root[lca(u,v)]-root[fa[lca(u,v)]]即可,思路比较简单。   [crayon···