【学习笔记】SAM
以 备 重 修（我觉得至少还得重修个三四次 QAQ）
OI-wiki（图片非常清晰直观）
几个概念/一点理解：
- $len[u]$ 表示以节点 $u$ 为尾巴的最长路径。也等于它插入时的字符串长度。
- 不恰当的比喻：$SAM$ 的肉体是一棵压缩的 $Trie$ 树，骨架是 $parent$ 树。
- 起点到每个终止节点是一条 $S$ 的后缀，每个节点代表某个长度为 $len[u]$ 的前缀的一些_长度大于某一长度的后缀_。更确切的，$u$ 表示的子串长度是 $(len[fa], len[u]]$ 范围内的。本质不同的子串数等于从起点出发的路径数，也等于 $\sum len[u] - len[fa[u]]$。（$SAM$ 当然是个 $DAG$ 啦
- 根据 $endpos$ 的概念，有祖先关系的节点 $endpos$ 是子集（完全包含）关系，没有祖先关系的节点 endpos 就是不交的。
- 每次加入一个节点最多会增加两个节点，空间复杂度是 $O(n)$ 的。
坑点：
- 空间两倍 QWQ
$CF1037H$
思路是贪心。
如果 $l = 1$，$r = n$，由于要找的是字典序严格大于 $T$ 的，我们考虑找一个 $S$ 的前缀，后面跟一个稍大的字符 $ch$。用 SAM 求出每一位的 $ch$，没有的话就是 $-1$. 最后倒着找第一个不为 $-1$ 的。
考虑 $l$ 和 $r$ 有限制怎么做，增加一步：找 $ch$ 的时候判断 $endpos$ 集合里有无区间 $[l, r]$ 的串。
$endpos$ 集合在这道题里必须求出，我们可以用经典套路——$parent$树上跑线段树合并。
$CF700E$
子串啊什么的考虑 SAM。
考虑到 $s_i$ 必然是 $s_{i + 1}$ 的前缀和后缀（不然削掉前/后缀不会更劣），在 $parent$ 树上体现为 $s_i$ 是 $s_{i + 1}$ 的祖先，于是想到 $dp$，找最长链
怎么判断出现了两次呢？记录任意一个 $s_{i + 1}$ 的位置，$endpos$ 集合用线段树合并，就能查询了。
$区间本质不同子串个数$
类似于“区间元素数”，我们离线询问，给每种元素选一个特征点，对于每个右端点维护左端点的答案。具体来说，每次更新以当前位置为右端点的串的 $lstpos$，一个长度为 $T$ 的串对左端点在 $[1, lstpos - T + 1]$ 的询问有贡献。
考虑 $SAM$，区间右端点右移至 $r$ 在 $SAM$ 上就要把一整条路径集合里的子串 $lstpos$ 更改为 $r$。暴力做显然补星。这是个链赋值操作，于是考虑 $LCT$ + $tag$。每个位置 $access$ 后到根的路径上 $lstpos$ 都相同，且代表的子串长度连续（根据 $endpos$ 的定义），可以直接区间修改区间查询。
$事情的相似度$
两个前缀 $x$ 和 $y$ 的最长公共后缀就是 $parent$ 树上的 $len[lca(x, y)]$。现在要求区间最深 $len[lca]$。
考虑离线询问，每次右移考虑 $r$ 的贡献。$SAM$ 上每个点维护它到目前被到达的最大时间，$LCT$ $access$ 赋值打标记（同一条链上的最大时间肯定相同），每次跳 $parent$ 树更新答案，注意更新的是一个区间的答案，线段树取 $\max$。
还有一种做法：容易想到 $dfn$ 序越近的对越优秀，不是最近的对对于答案没有贡献。想到启发式合并 $endpos$ 集合，$set$ 维护，找前驱后继。——查询区间啊，怎么办？注意到是三元组 $(l, r, v)$ ，丢到二维平面上二维数点就好。
记录 xml 的每日 sb：$parent$ 树上节点 $x$ 的祖先 $id$ 一定都小于 $x$，后代不一定小于 $x$。为什么？怎么建树的你看看去。 所以要处理一个按长度从大到小的操作序列。
都是两只 $log$ 的。因为「区间本质不同子串」写过第一种做法啦，这里想试试第二种！（哦呼
$BJWC2018-Border 的四种求法$
神题，比「区间本质不同子串」和「事情的相似度」高到不知道哪里去了。
往 $SAM$ 想，简直一脸蒙蔽啊。。这时候我们需要一些形式化：寻找最大的 $i$ 满足 $i - l + 1 \leq lcs(r, i)$，$lcs$ 是最长公共后缀
如果数据随机，那 $parent$ 树长得就比较平衡，树高 $log$，暴跳 + 查询每个 $r$ 的祖先 $endpos$ 集合里满足限制的 $i$ 最大值，线段树合并 $endpos$ 即可。
如果不随机呢？树高就 $O(n)$ 啦。不会做啦，$GG$ 啦。看题解啦。 题解
树分治/链分治，对重边的处理和轻边的合并及处理往往具有优秀的实现方法及复杂度，被套在树上问题也是很常见的啊啦啦！！
考虑一个询问查询了其子树的贡献和其所有祖先及祖先其他子树的贡献，子树贡献可以线段树合并照旧算。祖先呢？
考虑重链剖分后把询问复制 $log$ 份挂到祖先重链上（与它到根的路径交叉部分的末端），这样就只要分别处理每条链的询问了。总点数 $O(nlogn)$。
每条链从上到下把轻儿子的贡献合并进来，可以暴力插贡献因为轻儿子总数也就 $O(nlogn)$，拿一个下标为 $i$、权值为 $i - len[lca] + 1$ 的线段树维护区间最小值，这样查询在线段树上二分、根据最小值做出决策就可以了。
说说就好烦了呢qwq，写了一晚上 + 调了半个上午 200 行终于 AC 了呢qwq！多想，多思考。
$NOI2018-你的名字$
问啥？询问串有多少个子串不是另一个询问串的子串。我们要求的是用 T 的本质不同子串个数 - 两串本质不同公共子串个数。
假设 $l = 1$, $r = |S|$, 答案就是 $\sum\limits_{i = 2}^{T.cnt} max(0, len[i] - max(len[fa[i]], 第一次走到 i 的 T 串位置与 S 的 LCS))$ 为什么是第一次走到？第一次走到就是最远的嘛，是 $(len[fa[i]], len[i]]$ 的 $len[i]$ 而不是 $len[fa[i]] + 1$。为什么要最远？本质不同公共子串个数等于要在 $parent$ 树上取路径并啊。
若 $l$ 和 $r$ 任意，加一个线段树合并 $endpos$ 集合帮助在跳 $S$ 的 $parent$ 树时判断当前位置是否合法，就可以了。
广义 SAM！