(静态/动态)点分治 专题训练 数据结构

(静态/动态)点分治 专题训练

从成都集训后几天就开始学这个,发现细节非常多,不好处理,于是暂时弃坑了,现在重新捡起来,一定要刷掉。   静态点分治 处理的问题主要是和树上的路径有关,且树的结构不发生改变,点权边权等也不变。大体思路就是每次找到重心,处理过重心的路径并统计答案,递归进入子树。很多问题都涉及到要删除重复计数···
BZOJ2631 tree LCT+标记 数据结构

BZOJ2631 tree LCT+标记

LCT入门第二题,涉及路径上的基本标记操作。 个人认为坑点主要在乘法和加法标记的处理上。一开始采用的是加法操作遇到乘法标记就下放乘法标记,但是怎么调都过不去,和std拍了拍发现错的不太多,后来改成了两个标记同时存在,加法不影响乘法,但是乘法标记时要同时对加法标记产生影响,乘法时注意爆int的问题,也···
后缀数组 专题训练 字符串

后缀数组 专题训练

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

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

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

021017模拟 string 无旋Treap+并查集

区间翻转非常水,搞个无旋treap就好了,但是垃圾出题人居然卡常,没办法只能强开O3+节点内存池了。可以看出,在操作过后,问号之间形成了若干联通块,同一联通块内部所填字符必须相同,所以如果一个节点已经确定,那么整个联通块也就确定了,否则整个联通块随便填26个字母。 如果要求字典序第k小,就给并查集加···
BZOJ1500 [NOI2005]维修数列 无旋Treap 数据结构

BZOJ1500 [NOI2005]维修数列 无旋Treap

裸题,但是非常鬼畜,和线段树的“CPU监控”是同一程度的,都是要维护很多标记。 首先,先考虑要维护的标记: ml:最大左缀和,mr:最大右缀和,ms:最大中缀和; ※本题要求最大连续和不能为空。 sum:区间和; setv:区间修改标记; rev:区间翻转标记。 接着,考虑标记的作用范围。如果只考虑···
BZOJ4553 [Tjoi2016&Heoi2016]序列 树套树+三维偏序 数据结构

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

刚开始做的时候没好好地当作三维偏序来做,只是乱搞,后来膜了CDQ的思路,大概有了点套路,于是决定用树状数组套无旋treap来搞这道题(其实是因为还没打过CDQ呵呵)。 按照最长不降子序列的DP做法,DP方程显然为F[i]=max{f[j]}+1。问题转为了如何寻找最优的转移点j。 首先,按照套路,先···
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的分裂合并操作动态维护,最后二分答案就好啦。 ···
BZOJ2120&2453 数颜色 带修改莫队 数据结构

BZOJ2120&2453 数颜色 带修改莫队

带修改的莫队,在普通莫队的基础上增加了在时间轴上的滚动,将询问和修改分别记录,保存每个询问的左右端点,以及在当前询问之前进行了多少次修改,将块长设置为n^(2/3),保证理论时间复杂度是O(n^(5/3)),再将询问按照(左端点所在块,右端点所在块,时间),进行三元组排序,可以感性理解一下查询区间移···