Day1

最小公倍数 (multiple)

问题可以换个形式，便于之后的描述：

无向图中每条边的权值是一个二元组 $ (a, b) $。若干个询问，每次询问是否存在一条从 $ u \to v $ 的路径，使得 $ a $ 的最大值为 $ x $，$ b $ 的最大值为 $ y $。

一次询问会给定 $ u, v, x, y $，路径不要求是简单路径。

先不考虑 $ max a = x, max b = y $，只求 $ max a \leq x, max b \leq y $ 的话，是很简单的。离线，按 $ a $ 的顺序从小到大加边，维护 $ b $ 的最小生成树就可以。

再考虑原问题。假设按 $ a $ 的顺序加边，则我们需要找到一条边，使得能从 $ u, v $ 中的某个点出发，在最小生成树上到达某个点 $ r $，这个点与一条权值 $ a = x $ 的边相邻，且该边的 $ b $ 以及从 $ u, v $ 到 $ r $ 的路径上的 $ b $ 值不超过 $ y $ 。
我们在 $ a $ 相同的时候按 $ b $ 的顺序依次加入边以及处理询问。每次加一条边时，在 LCT 中染黑与这条边相邻的点。对于询问，将 $ u, v $ 分别提根，并询问是否存在一个黑点，使得其到根的路径上的最大值不超过 $ y $。这个不难完成。

至于 $ max b = y $，按 $ b $ 的顺序再做一次就好了。

~~时间复杂度 O(nlogn) 。~~

上述算法的复杂度应该是 $ O(n \log^2 n) $，因为要用堆维护子链。但依然有理论上的修正方法，即类似左儿子右兄弟，每次新建边时，两端的点也新建一份。这样每个点的子链个数降到 $ O(1) $，复杂度依然是 $ O(n \log n) $。

网络 (network)

对于每个询问，二分答案。则问题转化成：

设二分的答案为 $ K $，判断所有权值 $ > K $ 的路径是否都经过服务器 x 。如果都经过，则答案 $ \leq K $；否则 $ > K $ 。

实际上只需要对所有权值 $ >K $ 的路径求 路径交。
路径的交集依然是路径，用 RMQ 求 LCA 的话，在 $ O(1) $ 的时间内就可以求出两条路径的交集。
那用平衡树，或者离线离散化后用线段树，按权值的大小来维护二分结构就好。

时间复杂度 $ O(n\log n) $。

树 (tree)

将大树缩点。每个点看作一次复制的模板树部分。剩下的部分较简单，略。

时间复杂度 $ O(n \log n) $。

Day2

序列 (sequence)

莫队应该是很好做的。事先要预处理一些数据。

补充说明：对于分块后的每一组询问，固定左端点在块尾，右端点递增；对于每个询问，将左端点从块尾拓展到询问的左端点，回答询问后再还原到块尾，也就是类似树上分块莫队的做法。这样可以去掉删除元素的情况。同样的道理如果左端点固定在块头，右端点递减，则可以去掉添加元素的情况。

时间复杂度 $ O(n \sqrt{n}) $ 。

再提供一个 $ O(n \log n) $ 的算法，利用可持久化能够拓展到在线。

离线，按右端点排序处理询问。考虑每个元素 $ x $ 的贡献等于 $ (x - R)(L - x)a_x $，其中 $ R $ 为 $ x $ 之前的第一个不大于 $ x $ 的元素位置， $ L $ 为 $ x $ 之后的第一个小于 $ x $ 的元素位置。

维护一个函数 $ f(l) $，即右端点为 $ r $ 时，$ f(l) $ 表示询问 $ (l, r) $ 的答案。

每次加入最右端的元素 $ x $ 时，不难发现以这个新元素为末尾的所有区间的贡献对 $ f(l) $ 是一个如下的分段函数 $ g(l) $ ：

\begin{equation}
g(l) =
\begin{cases}
(x - R + 1)a_x, & l \leq R \\
(x - l + 1)a_x, & l > R
\end{cases}.
\end{equation}

这个 $ g(l) $ 实际上是一个标记。之后每次拓展右端点时，标记要复制一份，直到拓展到 $ L $ 。

注意到标记对 $ f(l) $ 的贡献是独立的，每次查询相当于单点询问。那只需要在线段树的节点上对这些标记永久化即可。

矿区 (mine)

自然，建出平面图的对偶图，这样就知道了每个矿区的面积和矿量。
然后，考虑从无穷域做 dfs 生成树并记录 dfs 序。这个 dfs 序包含所经过的点以及树边，且一条边在 dfs 序中恰好出现两次（拓展子树一次，回溯一次）。那么对于一个开发计划，也就是一个多边形，沿着 dfs 树走，则 dfs 树不断地往返于多边形外部和内部。
可以看出，这个多边形在 dfs 生成树的 dfs 序上，转化成了若干个区间，信息就存在这些区间中。区间的端点即多边形边界所经过的那些树边在 dfs 序中的位置。
剩下的就不用我多说了。

时间复杂度 $ O(E)-O(d) $ 。$ O(E) $ 是预处理平面图的复杂度。

大数 (number)

如果 $ p $ 不是 $ 2 $ 或 $ 5 $ ，那么显然 $ \forall k > 0, 10^k \not\equiv 0~ (mod ~p) $。

这样对于每个子串，前缀模 $ p $ 的值相同的话 $ p $ 就能整除子串的值。

预处理并离散化后，莫队就可以解决了。

时间复杂度 $ O(n \sqrt{n}) $。