利用主席树可以做到 $\mathcal{O}(n\log \Sigma)$ 空间，但是估计光常数就把复杂度还回来了（
by yllcm @ 2023-02-25 11:42:41
@[yllcm](/user/682934) 能细讲主席树做法吗，谢谢
by happybob @ 2023-02-25 11:44:11
@[happybob](/user/332914) SAM 需要支持的操作：添加一条链接，将一个点的所有链接复制到另一个结点上，对应到主席树就是单点修改和整棵树复制到另一个结点，假设是将 $q$ 复制到 $cl$ 执行 $rt_{cl}\gets rt_q$ 即可。不过我从来没用过（
by yllcm @ 2023-02-25 15:51:00
@[yllcm](/user/682934) 啊这
by happybob @ 2023-02-25 16:09:30