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

发布于 2017-12-06  3.88k 次阅读


联赛后最早刷的两个专题知识点,主要是通过比较麻烦的数据结构来提升代码能力。

基本上是按照做题的顺序来写的。


可持久化数据结构

bzoj 3123 [Sdoi2013]森林

给出一片森林,每个点有点权,要求支持动态连边操作,同时查询路径k小值,强制在线。

之前暑假做过弱化版,这道题就是动态维护倍增LCA,对每个点维护一颗到根的主席树,然后启发式合并(暴力插入),因为每个节点最多被插入O(logn)次,总共有n个节点,单次插入操作O(logn),所以总时间复杂度O(nlog^2n),可以接受。

 

bzoj 3166 [Heoi2013]Alo

题目比较麻烦,不再赘述。转换设问+单调队列+set预处理后,可以通过枚举次大值在一定区间内查询最大异或值,因此需要对01Trie进行可持久化,使其支持区间操作,之后就是作差查询即可,和主席树非常相似。

 

bzoj 3261 最大异或和

给出长度为n的序列,支持向最后插入一个元素,要求查询左端点在[l,r]之间,右端点为n的异或和,再异或x的最大值(好绕口)。

转换设问,维护前缀异或和,可持久化01Trie,差分一下作个差即可。个人感觉序列最前面那个边界比较麻烦,root[0]中一定要记着插0,负数用null就好了。

 

bzoj 4826 [Hnoi2017]影魔

读题非常恶心,画画图就好了。考虑枚举开区间的最大值,讨论不同范围内点对的贡献,先不管p1中相邻元素的贡献,只考虑“正常”的区间。假设我们当前的元素(下标,下同)为i,左边第一个大于它的元素为l,右边第一个大于它的元素为r,那么点对(l,r)的贡献为p1,左端点在[l+1,i-1]右端点为r的区间以及左端点在l,右端点在[i+1,r-1]的区间贡献为p2。那么,可以开主席树,通过标记永久化的区间加法,之后在两个值域均为[ql,qr]的范围内查询区间和即可。边界和细节非常麻烦,不存在最大的情况尤甚。

bzoj 2735 世博会

同样需要先转换设问,要求的就是:

$$min(\sum_{i=l}^{r}max(|a_i-a_0|,|b_i-b_0|))$$

其中,a0、b0可以是任意实数。

那么,max的部分可以看作平面上两个点(a0,b0)与(ai,bi)的切比雪夫距离,可以化为曼哈顿距离:

$$min(\sum_{i=l}^{r}|a_i+b_i-(a_0+b_0)|+|a_i-b_i-(a_0-b_0)|)*0.5$$

之后,高考数学教过我们数轴上到两个点距离和最小的点在两点中间那一段,但是我还是没想到接下来的部分:求数轴上一点到数轴上一些点距离之和最小

然后就是查询区间k小值了。只不过,因为要算距离,所以还要维护前缀后缀和,在求k小的时候一起算出来,线段树需要多维护一个区间和。但是这一部分我却调试了好久,对主席树的性质理解还是不够深入啊。

 

bzoj3221 Obserbing the tree树上询问

题目要求给路径上点权加上等差数列,查询路径点权和以及版本回溯(不删除)。

那么,首先来实现可持久化的区间加等差数列这个操作。类比于区间加法的标记永久化,每个节点维护覆盖当前区间的等差数列的首项及公差,同时维护子树和即可,查询时直接将每个节点对答案的贡献累加即可。

然后上了树,就要复杂一点了,首先要树剖提取区间,但是对区间操作还要区分序列随下标的增减性,然后还要考虑首项发生的变化,边界都搞掉以后也就没啥了,感觉非常繁琐。找了份std拍了好久,才发现是对回溯操作理解不对,本题的回溯操作并不是丢弃后面的版本,而是将指针指向当前版本,然后新建的版本依旧放在最后,这也就是给开了1280M内存的原因吧。

 

 


树套树

感觉好多题都一样,都是BIT/线段树套BST,所以这里就只放比较有意思的题。

 

BZOJ3295 [Cqoi2011]动态逆序对 && BZOJ2141 排队

BIT套treap,需要实现元素插入/删除,查询元素区间排名。

如果是删除元素,那么逆序对数一定不增,而且减少的逆序对数是该元素前且大于该元素的以及该元素后且小于该元素的,只要查询区间排名即可。

对于交换元素,对区间外是没有影响的,因为元素的相对位置并没有发生变化,所以我们只需要分类讨论元素位置变化对区间内逆序对的影响即可,依旧求区间内严格小于、大于该元素的元素个数,稍微复杂一点,代码只贴2141。

 

BZOJ3262 陌上花开

三位偏序裸题,求偏序对数即可,可用树套树水之,之前做过类似的,但是这道题麻烦的地方并不在于树套树,而是重复元素的处理。比如三个(1,1,1)对答案的贡献都是2。处理掉重复元素后,也就没啥可说的了。

BZOJ1146 [CTSC2008]网络管理Network

BIT+主席树(权值线段树),感觉是这里面最好的一道。

题目给出一棵有点权的树,要求动态修改点权,查询路径K大。那么如果直接上带修改主席树的话,单次操作影响的节点数太多,会导致MLE,这时候可以考虑别的套法。但是,如果还想用这种套法,就要用上差分的思想。首先,我们按照DFS序建出一颗静态的主席树(关于DFS序,可以直接树剖,还可以用来搞LCA,一举两得)。接着,如果我们将点u的权值从a改为b,那么只需要在BIT上的low[u]处线段树中权值为a的位置-1,b+1,同时在high[u]+1的位置进行相反的操作。这样[1,low[u]]的树状数组上的节点表示的就是u点到根路径上权值的变化量,因为只有u到根路径上的操作没有被抵消,那么只需要提取静态主席树还有树状数组的节点,然后O(log^2n)跑二分即可,时空复杂度都是O(nlog^2n)。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974