A
对于一个特定的 \(x\)，Piggy 总是会选择 \(p\) 使得 \(p\) 是质数，所以分数就是 \(x\) 的质因子个数。
容易发现至少有 \(t\) 个质因子的数是 \(2^t\)。最大的满足 \(2^t \le r\) 的整数 \(t\) 是 \(\left\lfloor\log_2 r\right\rfloor\)。
又因为 \(2l \le r\)，所以 \(\log_2 l + 1 \le \log_2 r\)，所以 \(\log_2 l < \left\lfloor\log_2 r\right\rfloor \le \log_2 r\)，所以 \(l < 2^{\left\lfloor\log_2 r\right\rfloor} \le r\)。
所以答案就是 \(\left\lfloor\log_2 r\right\rfloor\)。
时间复杂度：每个测试用例 \(O(1)\) 或 \(O(\log r)\)。
B
答案的每一个二进制位互相独立，所以可以分别计算答案在每个二进制位的取值。
设当前在考虑第 \(d\) 个二进制位，那么 \(a_i = \left\lfloor\frac{i}{2^d}\right\rfloor \bmod 2\)。
每过一秒，一个 \(1\) 会往左边和右边“扩散”\(1\) 格。
如果 \(a_n\) 一开始就是 \(1\) 那么答案的这一位就是 \(1\)。
否则 \(a_n\) 处于一个 \(0\) 的连续段中，我们需要计算这个连续段左边的 \(1\) 和右边的 \(1\) 能否“扩散”到 \(a_n\)。设 \(x = n \bmod 2^{d + 1}\)，那么 \(0 \le x \le 2^d - 1\)。左边的 \(1\) 扩散到 \(a_n\) 需要 \(x + 1\) 秒，右边的 \(1\) 扩散到 \(a_n\) 需要 \(2^d - x\) 秒。所以若 \(\min(x + 1, 2^d - x) \le m\) 那么 \(a_n\) 就能变成 \(1\)。特别地，若 \(n < 2^d\) 那么左边没有 \(1\)，所以这种情况若 \(2^d - x \le m\) 那么 \(a_n\) 就能变成 \(1\)。
时间复杂度：每个测试用例 \(O(\log (n + m))\)。
C
特判全是 \(-1\) 的情况。
考虑把所有值不是 \(-1\) 的位置提取出来，设其为 \(c_1, c_2, \ldots, c_k\)。\([1, c_1 - 1]\) 和 \([c_k + 1, n]\) 的 \(-1\) 是好处理的，不断乘 \(2\) 除 \(2\) 即可。容易发现 \([c_1 + 1, c_2 - 1], [c_2 + 1, c_3 - 1], \ldots, [c_{k - 1} + 1, c_k - 1]\) 的构造互相独立，所以我们现在只考虑解决 \(a'_1 \ne -1, a'_n \ne -1\) 且 \(a'_2 = a'_3 = \cdots = a'_{n - 1} = -1\) 的问题。
容易发现若 \(a_i\) 确定，那么 \(a_{i + 1}\) 只可能是 \(\left\lfloor\frac{a_i}{2}\right\rfloor, 2a_i, 2a_i + 1\) 其一。
发现 \(a_i \to a_{i + 1}\) 实质是在满二叉树上走了一条边。因此问题被转化成求一条满二叉树上给定起点 \(a'_1\)、终点 \(a'_n\) 和经过的点数 \(n\) 的路径。例如 \(a' = [3, -1, -1, -1, 9]\) 就相当于是找到 \(3 \to 9\) 在满二叉树上的一条经过点数为 \(5\) 的路径：
考虑先求出 \(a'_1 \to a'_n\) 在满二叉树上的最短路（可以先求出两点的 LCA，最短路就是 \(a'_1 \to \text{LCA}(a'_1, a'_n) \to a'_n\)），设其经过的点数为 \(l\)，那么无解当且仅当 \(l > n\) 或 \(l\) 和 \(n\) 的奇偶性不同。否则我们先把 \(a'_1, a'_2, \ldots, a'_l\) 填上求出来的最短路，然后在 \(a'_n\) 和 \(2a'_n\) 反复横跳即可。
时间复杂度：每个测试用例 \(O(n)\) 或 \(O(n \log V)\)。
D
\(a_i \cdot a_{i + 1} = a_j \cdot a_{j + 1}\) 的必要条件是无序对 \((a_i, a_{i + 1})\) 和无序对 \((a_j, a_{j + 1})\) 相同。事实上，若 \(a_i\) 都取质数，那么这个必要条件就会变成充要条件。
如果我们把 \((a_i, a_{i + 1})\) 看成一条边，那么问题变成找到点数最少的无向完全图（每个点还有一个自环），使得这个完全图存在一条经过 \(n - 1\) 条边且不经过重复边的路径。
考虑若完全图点数确定，我们如何计算这个完全图的最长不经过重复边的路径长度。
设完全图点数为 \(m\)，若 \(m\) 是奇数那么每个点的度数都是偶数，所以这个图存在欧拉路径，路径长度即为边数，其等于 \(\frac{m(m + 1)}{2}\)。
若 \(m\) 是偶数那么每个点的度数都是奇数，我们需要删除一些边使得这个图存在欧拉路径。容易发现一条边最多使奇度数点的数量减少 \(2\)，所以我们至少需要删除 \(\frac{m}{2} - 1\) 条边，删除 \((2, 3), (4, 5), \ldots, (m - 2, m - 1)\) 这些边即可，路径长度为 \(\frac{m(m - 1)}{2} - \frac{m}{2} + 1 + m = \frac{m^2}{2} + 1\)。
当 \(n = 10^6\) 时最小的 \(m\) 是 \(1415\)，第 \(1415\) 小的质数是 \(11807\)，符合 \(a_i \le 3 \cdot 10^5\)。
我们可以二分求出最小的 \(m\)，使用 Fleury 算法求出一个无向图的欧拉路径。
时间复杂度：每个测试用例 \(O(n)\)。
E
发现对于三条两两相交的线段 \((l_1, r_1, a_1), (l_2, r_2, a_2), (l_3, r_3, a_3)\)（不妨设 \(a_1 \le a_2 \le a_3\)），只用保留 \((1, 2), (2, 3)\) 之间的边，因为 \(a_3 - a_1 = a_2 - a_1 + a_3 - a_2\)，而且对于一个图的每个环，其中边权最大的边一定不会出现在最小生成树上。
由此，考虑这样的一个扫描线流程：每条线段在 \(l\) 处加入，在 \(r\) 处删除；加入一条线段时找到它按 \(a\) 排序后的前驱后继连边。实际上是维护每个时刻存在的所有线段按 \(a\) 排序后连成的一条链。
容易发现做完扫描线后边数缩减到了 \(O(n)\)，那么直接求最小生成树就行了。
时间复杂度：每个测试用例 \(O(n \log n)\)。
F
考虑 dp。设 \(f_{u, i}\) 为 \(u\) 子树内延伸上去的路径，钦定这条路径不包含 \(i\) 这个值，\(u\) 子树内除了这条路径的路径 MEX 和的最小值。\(i\) 的取值在 \([1, n + 1]\)。这样我们可以直接将这条路径的 MEX 当作 \(i\)，因为若 MEX 不是 \(i\) 那么 MEX 会更小，这个 dp 状态就不优。
考虑 dp 的所有转移：
- \(u\) 是叶子，则有：
- \(u\) 只有一个儿子，不妨设儿子为 \(x\)。令 \(\text{minx}=\min\limits_{i\neq a_u}{f_{x,i}+i}\)，则有：
- \(u\) 有两个儿子，不妨设两个儿子为 \(x,y\)。令 \(\text{minx}=\min\limits_{i\neq a_u}{f_{x,i}+i},\text{miny}=\min\limits_{i\neq a_u}{f_{y,i}+i}\)，则有四种转移方式：
- 延续 \(x\) 子树中的路径，即 \(\forall i\neq a_u,f_{u,i}=\min(f_{u,i},f_{x,i}+\text{miny})\)
- 延续 \(y\) 子树中的路径，即 \(\forall i\neq a_u,f_{u,i}=\min(f_{u,i},f_{y,i}+\text{minx})\)
- 新建一个路径，并将两个子树中的路径拼接起来，即 \(\forall i\neq a_u,f_{u,i}=\min(f_{u,i},\min\limits_{j \neq a_u}{(f_{x,j}+f_{y,j}+j)})\)
- 新建一个路径，并且不拼接两个子树中的路径，即 \(\forall i\neq a_u,f_{u,i}=\min(f_{u,i},\text{minx} + \text{miny})\)
令 \(k=\min(\min\limits_{i \neq a_u}{(f_{x,i}+f_{y,i}+i),\text{minx} + \text{miny}})\)，则可以将转移写成如下形式：
\[f_{u,i}=\begin{cases} \min(f_{x,i}+\text{miny},f_{y,i}+\text{minx},k), & i \neq a_u \\ +\infty, & i=a_u \end{cases} \]这样时间复杂度是 \(O(n^2)\) 的。
事实上可以证明我们只需要考虑不超过 \(O(\frac{n}{\ln n})\) 的 MEX（在 \(n = 25000\) 时只需要考虑不超过 \(3863\) 的 MEX），因此 dp 第二维只用枚举到 \(O(\frac{n}{\ln n})\)（或 \(3863\)）。
并且我们有一个能达到 \(O(\frac{n}{\ln n})\) 的 MEX 的一条链的构造，就是从 \(1\) 开始枚举 \(i\)，把 \(i\) 的因数倒序列举出来，比如 \([1, 2, 1, 3, 1, 4, 2, 1, 5, 1]\)。
时间复杂度：每个测试用例 \(O(\frac{n^2}{\ln n})\)。
关于 MEX 上界的证明：
只考虑链的情况。对于一个固定的 \(x\)，形如 \([a, \ldots, b, x, c, \ldots, d, x, e, \ldots, f, x, g, \ldots, h]\) 的序列，可以把它分成这样的段：
\[[a, \ldots, b], [b, x, c], [c, \ldots, d], [d, x, e], [e, \ldots, f], [f, x, g], [g, \ldots, h] \]其中不含 \(x\) 的段的 \(\text{MEX} \le x\)，含 \(x\) 的段的 \(\text{MEX} \le 4\)。
设答案为 \(t\)，那么 \(t\) 满足：（其中 \(c_i\) 为 \(i\) 的出现次数）
\[\min\limits_{i \ge 1} (c_i + 1) i + 4 c_i \ge t \]放缩，得：
\[\min\limits_{i \ge 1} (c_i + 1) (i + 4) \ge t \]进一步地，形如 \([b, x, c]\) 的段，若 \(x \ge 4\)，那么上面的 \(4c_i\) 可以变成 \(3c_i\)（因为 \(x\) 不可能为 \(1, 2, 3\)），所以得：
\[\min(\min\limits_{i = 1}^3 (c_i + 1)(i + 4), \min\limits_{i \ge 4}(c_i + 1)(i + 3)) \ge t \]那么：
\[c_i \ge \begin{cases} \left\lceil\frac{t}{i + 4}\right\rceil - 1 & 1 \le i \le 3 \\ \left\lceil\frac{t}{i + 3}\right\rceil - 1 & i \ge 4 \end{cases} \]也就是说我们需要 \(O(\frac{t}{i})\) 个 \(i\)，那么 \(n = O(t \ln t)\)，所以 \(t = O(\frac{n}{\ln n})\)。
我们还有：
\[n = \sum\limits_{i \ge 1} c_i \ge \sum\limits_{i = 1}^3 (\left\lceil\frac{t}{i + 4}\right\rceil - 1) + \sum\limits_{i \ge 4} (\left\lceil\frac{t}{i + 3}\right\rceil - 1) \]\(n\) 固定时可以二分出最大的满足上面条件的 \(t\)，得到 \(n = 25000\) 时 \(t = 3863\)。
标签：le,frac,min,题解,949,路径,Codeforces,ge,text From： https://www.cnblogs.com/zltzlt-blog/p/18231373