数据结构专题.
CF1192B
动态修改边权,查询树直径.
方法1:首先考虑常规的树上问题,即树剖一类方法不便于处理和合并直径这一类信息,于是考虑拍成序列做(树莫队就是这种想法).
考虑任一条路径是由左右端点和LCA连成,因此考虑可以用于求LCA的欧拉序列,刚好可以用差分法把任意一条路径表示成
\[dis_L+dis_R-2 dis_{LCA(L,R)} \]而且考虑一个区间内的\(L,R\),因为欧拉序列性质刚好 \(LCA\) 在序列中而更浅点不在,能让这条路径最大正是 \(LCA\) 位置,直接线段树求 \(\max (dis_L+dis_R-2dis_{mid})\) 即可.
具体实现方面,考虑维护的是三个元素的运算关系,因此不单要维护区间 \(max,min,ans\),要合并得到三元素的 \(ans\),需要维护一个二元素的中间变量,通过这些变量与单个元素合并来得出答案.
因此还维护区间内的 \(\max (dis_L-2dis_{mid})\) 和 \(\max (dis_R-2dis_{mid})\) 方便转移.
方法2:考虑从直径的性质出发:两颗树连接后,直径的端点一定出自这两个树的端点.因此可以直接在dfs序上维护,维护点区间的直径.利用直径性质,可以做到 \(logn\) 的 pushup.
启示:两种方法是树上维护问题的两种思考方式.
首先不是一般的树剖转DS思路.第一种从转化序列的方式切入,考虑求答案过程中的需求的量,就是LCA,于是自然过渡到欧拉序上问题.
第二种则直接对维护的答案思考,利用直径经典性质,发现直接维护是可行的.那就直接维护,虽然复杂度较高,不过思考过程够自然,场上得出概率也更大,应该会一下.
当然两种的思考流程是统一的,还是在传统方案无效,考虑新方法时,从矛盾的一般性中抓住矛盾点,然后根据特异的性质解决问题.
CF1039D
直接考虑问题时,一般会得到一个显然贪心,就是能加点的直接加,正确性没有问题,因此可以 \(O(n)\) dfs求出对于给定 \(k\) 的答案.
这时问题陷入一个瓶颈,就是原方法似乎没有向更小复杂度优化的空间了,同时这个贪心似乎也不能 DS 维护.而对连续 \(k\) 查询,想到在查询上做文章.
一般能想到两个方案,一个就是转移,从前一个答案经过修改改成后一个答案.在本题值得思考一下,不过感觉不太可行.
第二个就是考虑答案值域,发现答案 \(\frac{n}{k}\) 级别的,熟悉的形式,可以根号分治了.\(k\le \sqrt{n}\) 的部分直接算,后一部分在值域上想办法,发现答案是不增的,所以可以二分转折点把答案序列铺到 \(k\) 序列上.
多一个二分的 \(log\).略微卡常.较好的技巧是用dfs序优化掉递归的常数,效果非常显著.
P5309
Ynoi,根号复杂度,500ms,出题人nzhtl1477,值域2e5,要素非常齐全.
这道题确实是分块与根号分治搭配的一个好题.首先这种更新方式就很根号平衡,所以考虑根号分治.对于修改 \(x\) 大于 \(\sqrt{n}\) 的部分,可以直接暴力,这时需要一个 \(O(1)\) 维护区间加的 DS,这时就可以直接上分块了.
剩下的考虑 \(x\) 较小时的做法了.这种修改,在每 \(x\) 分一块情况下,每块内的修改都是等价的,只与 \(y\) 有关,而又有 \(y\le x\) 因此可以对于每一种 \(x\),维护一个长为 \(x\) 的块,用分块思维处理,需要前后缀和,直接维护即可.
然而这道题十分卡常,经二分块长可得,\(x\)较小部分常数较大,应该把阈值调小到 \(100-130\) 比较快,同时根号分治的阈值,和DS的块长不要共用,分块部分正常 \(\sqrt{n}\) 就行了.
CF983E
一道有思维含量和转化难度的题.
首先刚读题,有一种树剖维护染色的感觉,不过马上感觉不对劲.既然套路不是很管用,那就考虑用贪心,贪心地从当前点跳,跳到能走最远的位置,而因为一路上都可以换一条路径,所以找最远点是没有问题的.
进一步考虑,从最远点下车也是没有问题的,因为进一步跳,最优的方案一定包含从最远一点出发,因此一个简单的想法就是一路向上跳到需要的深度,这样得出的答案一定是正确的.
发现这个过程和倍增 LCA 有相似之处,也可以采用倍增的方法来维护,因此就可以做到 \(log\) 的跳路径了.
但是光能向上跳还不够,u和v同时跳到LCA之后,因为跳的是路径,不是连续的,有一个如何对接的问题,考虑让u和v高度低于LCA,此时u和v若在同一条路径上,就只需把答案 \(+1\) ,否则需要跳两次.如何维护这个问题,其实就是找有没有一个路径,一段在u子树,另一端在v子树.这个问题是可以二位数点的,不过可以用dfs序上主席树维护.
启发 此题的两步转化,一步是贪心跳链转倍增,一步是LCA位置讨论转DS维护.都有思维难度.关键在于敢想,然后就是有足够的经验去分析和寻找办法维护.
尤其是第二个转化.按照一般经验,这种位置的处理就是简单的讨论了,当发现简单讨论不能解决时,能否有耐心和勇气抽象出子问题,然后继续分析解决,就成了能否到达正解的关键.
总结
这几个题虽然不能说典,也是挺有启发性的.而且都是经过转化才有DS的出现.
对于隐藏在题目中的DS维护,可以把DS部分看成是原问题的一个子问题,考虑已知和要求,单独研究DS部分,再继续分析即可.
而对于DS问题的分析,暴力一般是显然的,至少在不属于数据结构问题的分析中已经得到了一个维护需求.这时也是有一个一般性和特异性的分析.在选取使用的结构时,要根据某种数据结构一般的性质和作用,去对应维护的需求,比如在根号分治需要 \(O(1)\)单点加时,应该敏锐地考虑分块的结构.在具体分析维护方式时,则要对问题具体分析,例如普通线段树的tag对子树,子树对父亲的两种更新.
其实DS本身是个比较套路的东西,所以转化要么是外层分析中,整体问题的改换,要么是具体分析中,小的子问题的解决.
标签：考虑,D9,二中,集训,LCA,维护,DS,根号,dis From： https://www.cnblogs.com/youlv/p/18261337