作者FRAXIS (喔喔)
看板Prob_Solve
标题Re: [问题] 第 k 大连续子阵列和
时间Fri Mar 6 22:38:45 2015
我在思考树上的 k 大路径时找到了一个比较容易做的o(n^2)方法。
（bzoj 3784）
用阵列的中点把阵列切成两半，计算通过中点的子阵列和，然後分别递回
两边计算不通过中点的子阵列和，就可以找到第 k 大了。
计算通过中点的子阵列和时，
把左半边每个元素到中点的子阵列和算出并排序，设为X。
把右半边每个元素到中点的子阵列和算出并排序，设为Y。
通过中点的子阵列和就可以被表示成 X + Y 了，是一个行与列都排好序的矩阵。
总共会有O(n lg n)个有序矩阵，在里面找出第 k 大可以在O(n lg^2 n)完成。
（理论上是可以O(n lg n)的，但是应该不实用）
同样的技巧可以解树上第 k 大路径，O(n lg^2 n)或是O(n lg n)。
也可以解树上 p-center（当然也可以解 path 上的 p-center）
树上的 p-center 有四种变化：V/V/p, V/E/p, E/V/p, E/E/p。
前三者可以在O(n lg^2 n)内解出，第四个是O(pn lg^2n)
（理论上可以在O(n)和O(n lg^2n)解出）
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.149
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1425652727.A.9F3.html