写在前面的话
\(\text{Rank2}\) ，\(100+100+30+0\) ，可惜还是太菜了。
发现自己的博弈论还是不会，并且做过的题目有点少。
最长不互质子序列
题目描述
现在有一个长度为 \(n\) 的序列 \(a\) ，我们希望找到一个最长的子序列满足相邻两个数不互质。求这个最长的子序列长度。
\(n , a_i \leqslant 10^6\) 。
思路点拨
我们考虑到一个数的质因子的数量是常数级别的，所以我们定义状态 \(f_i\) 表示子序列最后一个元素有 \(i\) 这个因子(\(i \in prime\)) 的最长上升子序列。那么以下标 \(i\) 为结尾的子序列长度就是：
接下来，我们用得到的这个 \(dp\) 值去更新即可。
时间复杂度是 \(O(n \log \log n)\) 的，因为我们需要用埃式筛找到每一个数的质因数有哪些。
数学课
题目描述
你有 \(n\) 个数 \(a_i\) ，你可以在相邻两个数之间添加一个运算符 \(+,-,\times\) ，问最后全部可能的表达式的值得和是多少。为了增加难度，有 \(q\) 次修改操作，每一次操作就是将原序列的一个 \(a_{pos}\) 修改为 \(k\) 。
\(n,q \leqslant 10^5\) 。
思路点拨
因为乘法有优先级运算，所以我们考虑将一堆数的乘法看做一个元素。那么如果一个元素前面可以填运算符（显然，是可以是 \(+,-\) 之一） ，那么就可以将这个运算符取反来抵消它产生的贡献。这就可以得出，一个数可以产生的贡献的前提就是它是序列的一段前缀积。答案可以表示为：
这里解释一下为什么会乘上 \(2\) ,因为一个元素之后不可以填 \(\times\) 发，不然有违背我们的定义。剩下的 \(n-i-1\) 个空位随便填咯。我们将前缀积 \(prod_{i=1}^{pos}a_i\) 的贡献看做 \(b_{pos}\) 这样答案就是 \(\sum_{i=1}^{n}b_i\) 。接下来我们考虑修改。
我们的答案只与前缀积有关，每一次修改的元素只会影响到一个 \(b\) 数组的后缀。我们进行区间除法，区间乘法即可，使用线段树优化。
时间复杂度 \(O(n \log n)\) 。
通缉
题目描述
有一颗树，树上的路径有长度。两个点之间的距离就是他们在树上的最短距离。
有 \(q\) 次询问，每一次询问给出四个参数 \(l1,r1,l2,r2\) ，保证 \(l1 \leqslant r2<l2 \leqslant r2\) 。问在 \([l1,r1]\) 之间选择一个节点 , \([l2,r2]\) 之间选择一个节点，他们的距离最大是多少？
\(n,q \leqslant 10^5\) 。
思路点拨
膜拜场切这题的巨佬ollo和_saltFish_。
我们对于点集合 \(A,B\) ，如果要选出两个点使得直径最大，那么从 \(A\) 中选出的点一定是虚树的直径的端点之一。并不难证明，画画图就理解了。
那么我们的答案就是将 \([l1,r1]\) , \([l2,r2]\) 的直径合并咯。怎么求出一个区间的点的直径呢？
考虑线段树，在查询的时候就可以合并直径（会用到树剖之类的算法），单次 \(O(\log^2n)\) 求出直径。
时间复杂度 \(O(q \log^2 n)\) 。