LuoguLOJ分析先考虑 $l=1,r=|S|$ 的情况。对 $S$ 和 $T$ 建 SAM。设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出：如果有对应的转移直接走过去，匹配长度加 $1$；否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$；如果跳到 $1$ 都没有...
998244353？998244353！
Luogu分析线段树合并。显然只有两种情况： $a$ 比 $b$ 不知道高明到哪去了、 $b$ 比 $a$ 不知道高明到哪去了。第二种比较简单。设 $a$ 的深度为 $dep[a]$ ，子树大小为 $sz[a]$ ，答案就是 $\min\{dep[a]-1,k\}\times (sz[a]-1)$ 。第一种的话，可以在 $a$ 的子树中随便选一个点和 $a$ 谈笑风生的点作为 $b$ ，然后...
LuoguBZOJ分析并查集+线段树合并。考虑怎么求出一个连通块内的第 $k$ 大值。如果有一颗对应的权值线段树，就可以很方便的求出来了。那么考虑怎么搞出这颗权值线段树。一开始对于每个点维护一颗线段树，每次合并两个连通块时，直接线段树合并即可。具体实现及细节见代码。代码//It is made by M_sea #include <algorithm> #include <...