[uoj#410][IOI2018]会议

这是个挺裸的题,但是我这个傻逼花了好长时间才A,可能主要原因是太长时间没写代码码力下降了。
设$f(l,r)$为询问$(l,r)$的答案(如果$l>r$则为$0$),如果$l\le r$那么对于任意一个$l\le x\le r,h_x=max_{l\le i\le r}\lbrace h_i \rbrace$,有$f(l,r)=min\lbrace f(l,x-1)+h_x(r-x+1),f(x+1,r)+h_x(x-l+1),h_x(r-l+1)\rbrace$,那么我们可以建笛卡尔树,每一个询问可以直接在上面分治解决,询问时间是$O($树高$)$的。
那么如果我们对$h_x$相同的节点进行随机化调整(类似treap),就会发现此时的期望树高变为了$O(max(hi)\lg n)$的,瞬间60分到手。(也可以使用其他类似的平衡树的思想建树,但是代码会比较难写)
然后考虑100分怎么做,为了简化问题我们可以先将每个询问分治一次,找到笛卡尔树上深度最浅的一个点x,且x满足$l\le x\le r$,然后将问题转化为求解$f(l,x-1)$和$f(x+1,r)$,这个可以考虑用线段树合并来做,建两棵,一棵维护当前树中的前缀答案,一棵维护后缀答案,然后在笛卡尔树上一边遍历一边维护。
然后考虑维护过程,可以发现有两种操作,一种是整棵树中每个元素依次和一个一次函数取min,一个是整棵树中所有元素加上某个值。
由于是笛卡尔树所以我们可以不用做线段树合并,直接对偶到一棵大的线段树上取做即可。然后这个问题可以用树套凸包来做。然后我就写到心态爆炸了。后来才知道有个叫李超树的东西可以来维护,代码好写很多。
总结一下步骤:
Step1:建出笛卡尔树
Step2:使用倍增或者dfs+二分找出每个询问第一次分的位置
Step3:遍历笛卡尔树然后用李超树求解问题。
总复杂度$O((n+q)\lg^2 n)$常数小,能过。听说有一个$log$的做法,我还不会。

Tagged with:

发表评论