bzoj4569: [Scoi2016]萌萌哒
- 传送门
- solution
(O(nlog n))的标算大家都知道了。。
说一个(log^2)的以及常数优化。
直接考虑优化暴力。
显然最多只用合并(n-1)次就可以了，所以在这(q)次询问中所要求合并的元素中，并不是所有的(这可能高达(nq))合并都是需要的，实际上大部分是不需要的。
所以我们考虑用线段树维护(hash)值，求一个LCP来跳过相同的一段。这样就必须把并查集改成链表的启发式合并。所以时间复杂度为(O(nlog^2 n(启发式合并)+(q+n)log^2 n(需要询问(q+n)次mathrm{LCP})))。
- 常数优化(hztOrz)
把询问LCP那一段改成分治来做，如果发现一段相同就直接不做了。这样感觉(qlog^2 n)会变得很不满，就跑得飞快了。