【2021Feb】可持久化数据结构泛做

【HEOI2013】Alo

老套路题了

维护一个双向链表,从 \(1\) 到 \(n\) 枚举当前值作为第二大的值,那么可控区间就是\([pre_{pre_i},nxt_{nxt_i}]\) 所以两边取一边即可

求异或最大值需要可持久化 \(trie\) 树,这个是 \(trivial\) 的

【Bzoj3321】Obserbing the tree树上询问

刚做过一个维护等差数列的题目,所以这个就又 \(trivial\) 了

树剖来维护路径,那么对于主席树上的每个点,维护 \(d[x]\) 为公差,\(tag[x]\) 为首项

查询答案套上标记永久化,同时对于路径修改考虑先把左右的子区间统计出来,一段一段该,这样首项可以方便地得到

注意这个题目的数组大小,我开到了 \(60N\) 才过,其实也是因为树剖的原因

【清华集训2014】玄学

假的强制在线令人想到计算几何乱写里面的凸包的一个题,那么考虑一样的维护套路:维护每个节点的 \(size\),如果满脸就合并

对于每次修改,维护 \((l-1,1,0),(r,k,b),(n,1,0)\) 表示三段的信息

归并的时候对于新的 \(k=mul(k_l,k_r),b=add(b_r,mul(k_r,b_l))\)

对于询问区间 \([l,r]\) 放到 \(\log\) 个点上二分 \(k\) 然后修改当前的 \(ans\) 即可

【WC2016】鏖战表达式

水高分容易 \(AC\) 难

用可持久化 \(fhq\ treap\) 做其实十分显然,所以 \(80\ pts\) 是 \(trivial\) 的

在 \(\texttt{mathew99}\) 的博客里面给出了卡掉的构造:先来一堆 \(ord=1\),再来一堆 \(ord=2\),一次类推,这样这个算法的复杂度到了 \(k\log n\)

而正解用了随机化:对于 \(fhq \ treap\) 的合并,这样写:

if((ord[l]==ord[r]&&rand()%(sz[x]+sz[y])<sz[x])||ord[l]<ord[r]) balabala...
else balabala....

这样单次复杂度期望 \(O(k+\log n)\)

证明?Itst说有2019/2018的论文,然而论文网址废掉了

记录两个 \(\texttt{fhq treap}\) 的手残的地方:

\((1)\) \(\texttt{split}\) 第二个的时候记得是 \(\texttt{split(x,size,x,z)}\)

\((2)\) 可持久化的时候 \(merge\) 写的可持久化后的点

【loj120】持久化序列

每次操作,更新原来的平衡树,删除就删除,添加就添加

Codeforces702F T-shirt

一开始得到一个二分的做法,但是发现这个没有单调性,所以就放弃了

换一个角度,\(fhq \ treap\) 对每个人的获得量和当前剩余的钱数进行维护

对于每个货物,二分得到买得起它的子树,打钱数减少和答案增加的标记

对于权值减少后的重复,也就是 \(cost\le v\le 2cost\) 的 \(v\) 暴力插入平衡树里面,剩下的因为肯定还是权值大的部分,直接合并

每次插入会导致 \(v\) 减少一半,所以复杂度是合法的

这个标记下方要注意,尤其是最后输出答案的时候要遍历全树下放标记

【Hdu6087】Rikka with Sequence

维护原始的平衡树来对付 \(3\) 操作,每次拆出来对应的区间合并就行

对于 \(2\) 操作,考虑 \(k<r-l+1\) 的时候这个区间是会被不断复制的

那么把区间分裂出来,然后倍增出来每段的树,最后统一合并区间即可

这里还有一个 \(trick\) 是定期重构,具体而言:

if(tot<M-N/3) rebuild(); 

其实代码不好写

上一篇:接口自动化增加jsonschema验证


下一篇:【fhq-treap】poj2892 Tunnel Warfare