线段树维护区间最大子段和。
观察到 $s_i$ 增大的时候能在雪地上走的范围也是在增大的，而当雪地上最长的不能走的范围超过了 $d_i$ 时 FJ 是走不到另一端的。
也就是说，只要存在一个连续段 $l \sim r$ 满足 $s_i < f_{l \sim r}$ 且 $d_i \leq r-l+1$ 时 FJ 就无法到达第 $N$ 块砖。
转换一下问题，对于 $i=1 \sim n$ 和一个序列 $a$ ，若 $s_i \geq f_i$ 令 $a_i = -\inf$ ，若$s_i < f_i$ 令 $a_i =1$ ，则当序列 $a$ 的最大子段和小于 $d_i$ 时，答案就为 $1$ 。
显然不能对每一个询问都按照如上方式去维护序列 $a$ ，那有什么办法能够复用状态或者是避免冗余运算呢？
根据本片题解开头提到的单调性，也就是说 $s_i$ 增大的时候 $a$ 中 $1$ 的数量是减少的，整个过程就像是 $1$ 在不断地被删除。
于是可以得到一个做法，将原序列和询问中的 $s_i$ 离散化，将 $s_i$ 在原序列中的每个位置存在 std::vector 中。
令 $a$ 全为 $1$ ，然后把所有询问按照 $s_i$ 从小到大排序，此时对于任意一个 $s_i$ ，将原序列中小于等于 $s_i$ 的数所对应的 $a_i$ 都设为 $-\inf$ ，可以用之前的 std::vector 很方便地实现，然后用线段树维护全局最大子段和。
每一次在线段树上删除的时间复杂度是 $\mathcal{O(\log n)}$ 的，由于排序后的 $s_i$ 是单调不降的，所以每个位置的 $1$ 最多会被删一次，最后总的时间复杂度是 $\mathcal{O(n \log n)}$ 的。 $\text{#Code}$
二分 + 线段树。
很有意思的一道题，对每个区间直接排序肯定是不行的，我们可以考虑一个弱化版的问题，若一个序列只有 $0$ 和 $1$ ，如何对它的任意区间进行排序。
显然，如果一个序列只有 $0$ 和 $1$ ，那可以用线段树查询该区间有多少个 $1$ ，然后根据是升序排序还是降序排序把这些 $1$ 放到区间的开头/末尾即可。
于是可以得到一个很神奇的做法，将询问离线下来，二分第 $q$ 个位置的数字，假设当前二分的值为 $mid$ ，就将序列中大于等于 $mid$ 的数都标记为 $1$ ，否则标记为 $0$ ，然后扫描每一个询问，按照上面的方法进行排序，到最后查询第 $q$ 个位置的值，若为 $1$ 则说明二分的值太小了，在右区间继续二分，否则说明太大了，在左区间二分，由于题目给定的是 $1 \sim n$ 的一个排列，所以这个做法是正确的。 $\text{#Code}$
后缀数组 + 二分。
总算把这题过掉了，但是用的是 84pts 的做法。
首先题目中让我们判断 $F(A) \leq F(C)$ 我们可以先倒序扫描一遍字符串，预处理出每个后缀的 $F(C)$ 的值，后缀中字符的奇偶性可以用树状数组维护，由于只有字符 'a'~'z' 所以预处理的时间复杂度是 $\mathcal{O(n \log 26)}$ 的。
接下来枚举字符串 $AB$ 考虑怎么复用之前的状态，可以再用一个以 $F$ 值为下标的树状数组去维护，假设当前枚举到位置 $i$ ，则树状数组维护的是“位置 $i-1$ 之前的前缀”有多少个前缀满足其 $F$ 值小于等于当前查询的 $F(x)$ 。
每次扫描到一个字符 $c_i$ ，枚举 $i+1$ 之后 $c_{1 \sim i}$ 的重复段，可以用哈希来判断，时间复杂度 $\mathcal{O(n \ln n)}$ ，每次枚举时都可以得到一个后缀 $C$ ，而 $F(C)$ 我们已经预处理好了，直接在维护 $F$ 的树状数组上查询 $F(C)$ 即可，此时查到的是位置 $i-1$ 之前的前缀对答案的贡献，因为题目中要求拆分出一个字符串 $B$ ，若此时将第 $i$ 个位置算进去肯定是不合法的，所以应当在计算完贡献之后再将 $c_i$ 的贡献加入树状数组中。
至于如何维护 $c_{1 \sim i}$ 的奇偶性，再开一个树状数组维护就行。
时间复杂度为 $\mathcal{O(n \ln n \log 26)}$ ，开 -O2 松过去了。
$\text{#Code}$
2-SAT
2-SAT
主席树 + ST 表。
稍稍展开一下，设 $lst_i$ 表示上一个与 $a_i$ 颜色相同的位置，特别地，若 $\min\{a_{lst^\prime_i} \sim a_i\}
现在问题就转变成了给定一个区间 $l \sim r$ ，求 $\sum_{i=l}^r[lst_i< l ] $ ，这东西用主席树随便维护一下就行。 $\text{#Code}$
0/1 分数规划
2-SAT
把每个评委的条件看作一个“或”类型的命题限制，然后将每道菜（包括满式和汉式）拆成两个点，分别表示选/不选该道菜。
首先，“或”类型的限制可以拆成两个“若 $p$ 则 $q$ ”的命题：
$$p \lor q \Rightarrow \begin{cases}\lnot p \rightarrow q \\ \lnot q \rightarrow p\end{cases}$$
直接将其连单向边即可，但是注意题目中有一个隐藏条件，也就是对于一个食材只能选择一种做法，也就是说，要将每个食材其中的一种做法和对应的另一种做法连单向边。
具体地说，若选择汉式做法，则不能选则满式做法，若选择满式做法，则不能选择汉式做法。
同时将上面两个命题的逆否命题也连上单向边，若不选择汉式做法，则必须选则满式做法，若不选择满式做法，则必须选择汉式做法。
然后直接跑 $\mathtt{tarjan}$ 缩点即可。 $\text{#Code}$
分治。
欧拉序 + 树上莫队。
莫队 + 值域分块。
首先这题可以很容易地得到一个莫队的做法，每次移动左指针和右指针的时候用数据结构维护对应区间内的值域，不难想到用树状数组维护。
但是这样会导致每一次移动指针的时间都是 $\log n$ 的，总的时间复杂度就是 $\mathcal{O(n\sqrt{n}\log n)}$ ，显然无法承受。
于是我们可以使用值域分块，每次修改操作是 $\mathcal{O(1)}$ 的，查询操作是 $\mathcal{O(\sqrt{n})}$ 的，由于对于每一个询问我们只需要查询一次，而指针移动的时间是 $\mathcal{O(1)}$ 的，所以时间复杂度就降到了 $\mathcal{O(n\sqrt{n})}$ 。 $\text{#Code}$
树剖 + 树形 dp
题目有两问，分别让我们判断可达性和最近的可达给定点，第一问很简单，以 $E$ 点为根跑 dfs ，然后对于每一个询问用 dfs 序判断点是否在被断开的边中以深度较大的那个点为根的子树内即可。
考虑怎么解决第二问，第二问要求当前节点所在连通块中最近的给定点，首先可以用树形 dp 求出所有的点到他们子树内最近的给定点是哪个，转移方程如下：
$$f_u=\min_{v\in Son_u}\{f_v+z\}$$
接下来我们要考虑答案可能会出现在什么位置，若最近的给定点在当前询问点 $x$ 的子树内，那么答案就是 $f_x$ ，若不在，那么路径必定经过断开点到 $x$ 点的路径上，用树链剖分维护一下链上 $f_{u}$ 的最小值，但是注意到 $x$ 点到链上的节点也有一段距离，所以我们可以维护链上的 $\min\{f_u-dis_{1,u}\}$ ，计算答案的时候加上 $dis_{1,x}$ 容斥掉就行。
维护链上最小值，由于没有修改，所以我用的是 ST 表。 $\text{#Code}$
先丢个结论吧，答案是 $\dbinom{n}{4}+\dbinom{n}{2}+1$ ，暂时不会证，咕一会。
树状数组好题。
首先看一下正常的逆序对怎么求，设 $c_i$ 表示下标在 $i$ 之前的元素有多少个比 $a_i$ 大，显然逆序对的数量就是 $\sum_{i=1}^nc_i$ ，接下来考虑一轮冒泡排序会对 $c_i$ 造成什么影响。
观察冒泡排序的过程，每一次都比较相邻的元素，并且把大的元素向后移，而当一个正在“冒泡”（也就是从前向后移）的元素只有在它前面有一个比它大的元素时才会停下，也就是说，此时该元素前已经没有元素比它大了。
推广到一般元素，在经过一轮冒泡之后，所有非零的 $c_i$ 都减少了 $1$ ，继续推广到 $k$ 次的情况，所有小于等于 $k$ 的 $c_i$ 都减少至 $0$ ，所有大于 $k$ 的 $c_i$ 都减少了 $k$ ，所以可以直接推算 $k$ 轮冒泡之后的逆序对数量：
$$\sum_{i=1}^nc_i-\sum_{c_i\leq k}c_i+\sum_{c_i > k} k$$
上式可以开两个权值树状数组维护，记得特判 $k>n$ 的情况。
接下来考虑如何处理交换操作，由于一次交换只会影响到一对逆序对，所以直接对 $c_i,c_{i+1}$ 进行分类讨论修改即可，同时在两个树状数组上处理 $c_i,c_{i+1}$ 变化造成的影响。 $\text{#Code}$
求基环树直径。
首先考虑直径会由哪些部分构成，讨论以下两种情况：
直径不经过环
直径经过环
对于第一种情况，先把环取出来，然后对环上每一个节点对应的子树都跑一遍树形 dp ，求出每个子树的直径，取最大就行。
接下来看第二种情况，第二种情况一定是由两个环上的点到其子树中的最长路径和这两个点在环上的一条路径拼凑而成，我们可以将环上每个节点到其子树中的最长路径当作点权挂在点上，然后根据处理环形问题的一般套路，选一条边断开形成一条链，然后复制一倍接到链的后面。
设链上的节点为 $1\sim n$ ，节点 $i$ 的点权为 $f_i$ ，链上边权的前缀为 $s_i$ ，于是我们可以这样 dp ：
$$ans=\max_{\frac{n}{2} < j < i}\{f_i+f_j+s_i-s_j\}$$
发现这个限制很像单调队列优化 dp ，我们可以把定值 $f_i+s_i$ 提出来，然后用单调队列求 $\max_{j=\frac{n}{2}+1}^{i-1}\{f_j-s_j\}$ 就行。
注意处理一下二元环的情况，我并不想使用通过成对存储的技巧去处理重边，由于在一个基环树中二元环最多只有一个，而这题的输入又按照顺序给出，所以可以将输入的边离线下来再对每一条边通过映射关系判断是否出现重边，若有重边则该边边权取两条边的最大值。
回答询问时对于有二元环的连通块直接跑树的直径求解即可。 $\text{#Code}$
线段树合并。
线段树合并。
对于每一个连通块都开一棵权值线段树，下标为岛的重要值，这样就可以直接查询该连通块中第 $k$ 重要的岛了。
对于合并操作，用并查集维护连通性，同时记录每个连通块的大小，用于判断无解。然后用线段树合并把两个连通块的权值线段树合并起来就行，记得用动态开点线段树。
时间复杂度为 $\mathcal{O(n\log n)}$ 。 $\text{#Code}$
线段树套 $\mathtt{01\ Trie}$
区间 $l \sim r$ 的限制很好解决，对于线段树的每一个节点都开一棵 $\mathtt{01\ Trie}$ ，查询的时候将 $l \sim r$ 划分成若干个线段树节点上的区间，然后在这些节点对应的 $\mathtt{01\ Trie}$ 上查询即可。
对于单点插入操作，由于每次修改都会在线段树的节点上产生一条从上到下的路径，将要插入的值直接插入路径上所经过的节点对应的 $\mathtt{01\ Trie}$ 。
但是题目还有一个时间限制，只能购买个固定时间段内的商品，不难想到使用可持久化数据结构，但是那东西调起来太麻烦了，于是可以使用下面这种方法:
题目要求的是一段时间的后缀，所以直接在普通 $\mathtt{01\ Trie}$ 上的节点打标记，标记这个节点最后被更新的时间是多少，每次查询的时候直接跳过不在给定时间范围内的节点就行，而对于特殊商品，设他们被更新的时间为 $\inf$ ，这样就可以保证每次查询时一定能与特殊商品进行最大异或匹配。
由于值域与 $n,m$ 同阶，所以总的时间复杂度是 $\mathcal{O(n\log ^2 n)}$ 。 $\text{#Code}$
$\mathtt{kruskal}$ 重构树
首先对原图跑一遍堆优化的 $\mathtt{dijkstra}$ ，求出所有点到节点 $1$ 的最短路，然后对原图按照海拔从高到低建出 $\mathtt{kruskal}$ 重构树，此时这棵树的非叶子节点部分构成了一个小根堆，堆顶节点的权值表示图中海拔最低的边，而树上任意两个叶子节点的 $\text{lca}$ 的权值表示原图中两点之间路径上海拔最低的边的最大值。
接下来考虑如何处理询问，对于询问中的出发点，找到 $\mathtt{kruskal}$ 重构树上对应的叶子节点，然后用倍增跳到根节点到该叶子节点的路径上满足该点权值大于当前水位线的深度最低的节点，此时该节点子树中的叶子节点就是从该出发点出发能够开车到达的所有节点，答案就是这些节点与节点 $1$ 的最短距离最小的那个点到节点 $1$ 的最短路的长度。
那怎么求出这个值呢？用树形 dp 预处理一遍就可以了，总的时间复杂度为 $\mathcal{O(n \log n)}$ 。 $\text{#Code}$
线段树 + 尺取法
首先将区间离散化之后按照长度排序，这样就可以保证最后一定是大区间减去小区间。
排序之后用双指针扫描所有的区间，首先固定左指针，右指针单调向右移动，就可以找到在固定最小区间时需要多大的区间才能使序列中某个位置被覆盖超过 $m$ 次。维护区间覆盖的过程可以很容易地使用线段树去维护。而由于两个指针移动的方向都是单调的，所以每个区间最多被覆盖/清除一次，所以时间复杂度为 $\mathcal{O(n\log n)}$ 。 $\text{#Code}$
决策单调性。
$\mathtt{kruskal}$ 重构树
虚树
快被单调栈建树搞晕了，于是我选择用 std::sort 。
具体做法是将询问中的点按照 dfs 序进行一次排序，构成一个点集 $S$ ，然后将该点集中相邻两点的 $\text{lca}$ 也加入到点集中，去重之后再排一次序，得到点集 $S^\prime$ ，此时该集合中相邻两个元素 $S^\prime_{i-1},S^\prime_{i}$ 的 $\text{lca}$ 就是虚树上 $S^\prime_{i}$ 的父节点。
虚树上相邻两点之间的边权设为两点在原树中路径上权值最小的边，然后在这棵虚树上跑一遍树形 dp ，设当前点为 $x$ ，$f_x$ 表示使 $x$ 不与其子树中任意一关键点联通的代价，枚举 $x$ 的子节点 $y$ ，$z$为 $x,y$ 之间的边的边权：
若 $y$ 为关键点，则 $z$ 必须被断开。
否则可以选择断开 $z$ 或者在 $y$ 的子树中断开一条边，取最小即可。
于是得到转移方程：
$$f_x=f_x+z$$
$$f_x=f_x+\min_{y \in Son_x}\{f_y,z\}$$
总的复杂度为 $\mathcal{O(n \log n+\sum k \log k)}$ ，由于虚树的大小是 $\mathcal{O(k)}$ 的，而 $\sum_{i=1}^n k_i\leq 10^5$ ，所以可以通过本题。 $\text{#Code}$
dfs序 + 平衡树
虚树 + 树上差分 + 线段树合并
首先将问题抽象，给定一棵 $n$ 个点的树和 $m$ 条树上路径，问有多少有序点对 $(i,j)$ 满足这两点同时被至少一条路径覆盖。
于是可以得到一个转化的问题，对于每个点求出覆盖该点的路径并的大小减一，加起来除以二就是答案（将无序点对转化为有序点对）。
然后观察到覆盖该点的链并一定是一个以路径端点为叶子节点的生成树，根据虚树的思想，可以以路径端点为关键点建出一棵极小连通子树，这棵极小连通子树的大小就是路径并的大小，而树上的边数等于点数减一，所以只要求出这棵极小连通子树上的边数就可以求出该点对答案的贡献。
首先有一个经典结论，对于一棵树上的任意一个点集 $S$ ，将其中的元素按照 dfs 序排序之后得到一个有序不可重集合 $S^\prime=\{a_1,a_2,a_3,\dots,a_n\}$ ，此时设这些点在树上的极小连通子树为 $T^\prime=(V,E)$ ，有：
$$|E|=\dfrac{dis(a_1,a_2)+dis(a_2,a_3)+\dots+dis(a_n,a_1)}{2}$$
为什么这样做是正确的呢，感性理解一下就是在按照集合中点的顺序遍历这棵极小连通子树时是按照 dfs 序来遍历的，所以每条边都会被经过正好两次，所以除以二之后就是极小连通子树上边的数量。
接下来考虑怎么维护 $|E|$ ，对树上每个节点以 dfs 序为下标建出一棵动态开点线段树，用线段树维护这个有序点集，线段树的叶子节点表示该 dfs 序对应的节点是否存在与集合当中，而其上级节点保存该节点对应的 dfs 序区间中的点构成的点集的相邻元素之间的路径和，合并信息后，最上层的节点保存的信息应当是 $dis(a_1,a_2)+dis(a_2,a_3)+\dots+dis(a_{n-1},a_n)$ 。
由于在线段树上上传信息时可以看作两个区间的合并，利用分治的思想考虑怎么合并这两个区间代表的点集，可以对每个线段树上的区间记录在这个区间中 dfs 序最小和最大的元素，合并区间时加上左区间中 dfs 序最大的元素和右区间中 dfs 序最小的元素之间的距离即可，可以通过求 $\text{lca}$ 实现。
观察到增加一条路径需要修改路径上所有点的线段树的信息，如果直接维护那肯定是要超时的，发现静态的“增加路径”是可以使用树上差分维护的，那又怎么维护节点上线段树的信息呢？用线段树合并即可！
于是我们得到了一个这样的算法：
对树上每一个节点建以 dfs 序为下标的动态开点线段树。
读入路径的信息，差分维护路径，具体操作就是在路径端点对应树上节点的线段树上增加路径端点的信息，在路径端点的 $\text{lca}$ 和 $\text{lca}$ 的父亲处删去路径端点的信息。
对整棵树自底向上地进行线段树合并，通过线段树上保存的信息计算每个点对应的路径并的大小，记得手动加上 $dis(a_n,a_1)$ ，将值除以二之后得到 $|E|$ 。
将每个节点对应的 $|E|$ 加起来除以二就是答案。
具体实现的时候有一些小细节，比如 $\text{lca}$ 的父亲不一定存在，不能直接进行修改，可以将修改信息通过 std::vector 挂在对应的节点上，在合并的时候进行操作即可。
求 $\text{lca}$ 的时候使用 $\mathcal{O(1)}$ 的 ST 表，总的时间复杂度降至 $\mathcal{O(n\log n)}$ 。 $\text{#Code}$
广义决策单调性。
首先有一个很暴力的 dp ，首先将序列 $a$ 按照升序排序，设 $f_{i,k}$ 表示在前 $i$ 个村庄建 $k$ 个邮局的最近距离总和，可以这样转移：
$$f_{i,k}=\min_{j=0}^{i-1}\{f_{j,k-1}+w(j+1,i)\}$$
$w_{l,r}$ 表示在区间 $l \sim r$ 设置一个邮局， $l \sim r$ 中的村庄到该邮局的距离总和的最小值。显然邮局应该设置在中位数的位置。
然后发现因为对于一个给定的区间，邮局设置的位置是固定的，所以 $w_{l,r}$ 可以递推求出：
$$w(l,r)=w(l,r-1)+a_{r}-a_{mid}$$
这样做的正确性跟 $r$ 的奇偶性有关，在此不作展开，递推预处理的时间复杂度是 $\mathcal{O(n^2)}$ 的。
此时我们得到了一个 $\mathcal{O(n^2k)}$ 的做法，考虑如何优化。
我们发现 $w(l,r)$ 这东西是满足四边形不等式的，证明如下：
$$w(l,r+1)-w(l,r)=a_{r+1}-a_{\frac{l+r+1}{2}}$$
$$w(l+1,r+1)-w(l+1,r)=a_{r+1}-a_{\frac{l+1+r+1}{2}}$$
两式相减：
$$w(l,r+1)-w(l+1,r+1)-w(l,r)+w(l+1,r)=a_{\frac{l+1+r+1}{2}}-a_{\frac{l+r+1}{2}}$$
由于序列 $a$ 单调不降，所以：
$$a_{\frac{l+1+r+1}{2}}-a_{\frac{l+r+1}{2}}\geq 0$$
故：
$$w(l,r+1)-w(l+1,r+1)-w(l,r)+w(l+1,r)\geq 0$$
移项得：
$$w(l,r+1)+w(l+1,r)\geq w(l+1,r+1)+w(l,r)$$
$$w(l,r)+w(l+1,r+1)\leq w(l+1,r)+w(l,r+1)$$
满足四边形不等式。
于是有：
$$p_{i,k-1}\leq p_{i,k}\leq p_{i+1,k}$$
在范围内枚举 $p_{i,k}$ 即可，可以证明枚举的决策点的个数上限是 $(n+1)\ast (n+k+1)+nk$ 的。
时间复杂度降至 $\mathcal{O(nk)}$ 。 $\text{#Code}$
离线 + 树状数组。
矩阵树 + 容斥。
有一个直观的想法是将所有公司的边都丢进基尔霍夫矩阵中暴力消元，但是发现这种做法会把一个公司建设了多条道路的情况也算进去。
考虑容斥计数，设 $S$ 表示所有的公司的集合，$f(S)$ 表示 集合 $S$ 中的公司在不考虑要求的前提下建设道路的方案数，则答案为：
$$ans=\sum_{T\in S}(-1)^{|S\backslash T|}f(T)$$
直接暴力枚举集合即可，时间复杂度为 $\mathcal{O(2^nn^3)}$ 。 $\text{#Code}$
预处理矩阵 + 分组转移。
观察到 $2,3,4$ 的最小公倍数为 $12$ ，根据这个性质，我们可以预处理出前十二个矩阵，然后直接转移就行。 $\text{#Code}$
离散化 + 动态开点线段树。
首先求出序列 $a$ 的前缀和 $s$ ，于是问题就转化成了求有多少对 $l,r$ 满足 $L\leq s_r-s_{l-1} \leq R$ 。
将式子移项，将 $r$ 固定，问题就转化成了对于一个给定的 $r$ ，求有多少个 $l$ 满足 $s_r - R \leq s_{l-1} \leq s_r -L$ ，用动态开点的值域线段树即可。
关于实现方面的细节，由于是动态开点，所以离散化不一定是必须的，但是时间复杂度会变成 $\mathcal{O(n\log V)}$ ，其中 $\mathcal{V}$ 为值域。
离散化之后，时间复杂度降至 $\mathcal{O(n \log n)}$ 。 $\text{#Code}$
点分治。
[AGC003E] Sequential operations on Sequence
单调栈 + 差分。
点分治。
首先考虑如果只有 $w$ 一维的限制该怎么做，就是点分治的板子，对于每个分治重心，处理出当前分治区域内的点到分治重心的 $w$ 值和 $l$ 值的和，排序之后用双指针扫描一遍就行。
将 $w$ 从小到大排序之后用一个左指针单调向右扫描，右指针指向当前序列中的最大的能与 $w_l$ 相加之后小于等于限制的值的位置，形象地说就是：
$$ w_l + w_r \leq w_{\lim}\ ,\ w_l + w_{r+1} > w_{\lim} $$
由于 $w$ 是单调递增的，所以右指针单调向右移，当没有 $l_{\lim}$ 的限制时，区间 $w_{l+1 \sim r}$ 中的点都能与 $w_l$ 匹配形成一条经过分治重心且 $\sum w \leq w_{\lim}$ 的路径。
接下来在 $w_{\lim}$ 的限制下考虑 $l_{\lim}$ 的限制，也就是说我们要知道在 $w_{l+1 \sim r}$ 这些值对应的点中有哪些点能与左指针的点匹配形成一条 $\sum l \leq l_{\lim}$ 的路径。
由于 $l$ 值的上限是 $10^5$ ，所以可以将 $l$ 映射到树状数组上，可以将 $l$ 值作为树状数组下标，一开始将序列上的点的 $l$ 值都加入到树状数组中，当左右指针向中移动时就一个一个地将点对应的信息从树状数组上删去。
匹配时树状数组维护的信息就是左右指针对应地区间中的点的信息，于是直接查询有多少点能与左指针指向的点匹配即可。
具体实现有一些小细节，可以参考代码，时间复杂度为 $\mathcal{O(n\log^2 n)}$ 。 $\text{#Code}$
差分 + 树剖。
$\mathtt{Link/Cut\ Tree}$
子序列自动机 + $\mathtt{Trie}$
鄂公网安备 42010202000505 号