已完成 $SA$ 大学习。

$SA$，顾名思义，$Suffix \ Array$，就是后缀数组的意思。

我们先来考虑一个问题。给定一个字符串，多次询问，要我们求出两个后缀的 $\operatorname{lcp}$（最长公共前缀）。

先将字符串的每一个后缀全部插入一颗 $\operatorname{Trie}$ 树。可以发现询问就等价于询...

题意： 给定字符串 $s$。总共 m 个询问，每次给定 $a, b, c, d$，问你子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少。 $1\le n,m\le 100,000$，$a\le b$，$c\le d$，$1\le a,b,c,d\le n$。

很有意思的一道题。 首先，看到字符串的题就可以先盲猜二分。显然这道...

题意：找有向图上平均值最大的环。 首先，看到平均值，可以想到分数规划。所以二分，判断是否有负环即可。 使用 dfs 判断，复杂度 $O(nm \log V)$

一道很有意思的题。

先让我们来观察一下。题目说的这个树是一个二叉树，所以每个点的度数小于等于三。

然后，题目要求我们找到一个树里面的点。并且只有 $\log n$ 次询问机会。$\log n$，定位某个点。好像在哪里见过？这很像 P4886。那道题我...

A： 显然两个数最后都要变成它们的 lcm。

B： 前 m - n 秒显然没用，最后 n 秒贪心抢蛋糕即可。

C： 注意到操作一相当于 $x \to \frac{x}{2}$，操作二相当于 $x \to 2^k + \frac{x}{2}$。所以直接二进制分解一下就行。

D： 如果 $\exists i, b_i > b_{i +...

1. 树分治

树分治是一种统计树上路径的方法。

例题：P2634 这道题要求我们统计树上长度为 3 的倍数的路径的个数。设 $(u,v)$ 表示 $u$ 到 $v$ 的路径。让我们先来考虑怎么统计满足 $lca(u,v) =...

设每条边的边权是边的编号。按照边权从大到小建出 kruskal 重构树。让区间联通相当于求出区间所有点在重构树上的 lca 的点权。求一下即可。

A： 水题没价值

B： 首先，如果存在 $l,r$，满足 l 到 r 中间的所有数都是 1，则显然无解。否则只要满足对于每个 $s_i = 1,s_j = 0$，$p_j > p_i$，p 就可以满足条件了。用堆做就行了。

C: DP 即可。

D: 走到左下角和右上角。然后距离最近的点一定是截距最大或最小的点。然后算一下就可以了。<...