开喷。 出题人你 O(nlog⁡3n)O(n\log^3 n)O(nlog3n) 大常数的解法开 2×1052\times 10^52×105 时限还只给 1s 是何意味？！ 注意到 STD 是按字典序排序的，这个不是在 100 年前就被 hack 了吗？ 例如 按照官方题解来排是 1 3 2 3 2 1，但显然可以顺序遍历做到 1 3 2 1 3 2 我认为这道题正确解法应该是： * 首先发现是拼数的问题转到了树上，所以应该按 S+T<T+SS+T\lt T+SS+T<T+S 排。暴力是 O(n2log⁡n)O(n^2\log n)O(n2logn) 的。 * 然后考虑启发式合并，依旧记录前缀哈希值。合并是 O(nlog⁡2n)O(n\log^2 n)O(nlog2n) 的。 * 排序时，先用原串 O(nlog⁡2n)O(n\log^2 n)O(nlog2n) 把非重儿子排个序，然后重儿子再用 Treap+哈希二分排序，这个也是 O(nlog⁡2n)O(n\log^2 n)O(nlog2n) 的。 这样子就能做到 2log 了。官方题解写的是啥子啊。 前面忘了后面忘了，买个 plus 吧。