UOJ Round #13
A. Yist
30
$n \le 15$
状压所有可能的子序列，时间复杂度 $\mathcal O(2^n poly(n) + q)$。
60
$n \le 1000$
二分 $x$，每次贪心删除最小数，判断是否可行。
时间复杂度 $\mathcal O(n^2 \log n)$。
90
$n \le 300000$
小数会限制大数的删除，因此从小数开始考虑。
在序列左右都加上一个无穷小且不删除，找到它左右两边第一个未删除且比它小的位置 $u, v$，那么区间长度就是 $(u, v)$ 这个开区间的长度减去区间中比它小且被删除的数个数，答案为所有数对应的区间长度最小值。
从小到大加入，用树状数组或者什么其他数据结构维护一下即可求出区间中所有比它小且需要删除的数的个数。
时间复杂度 $\mathcal O(q n \log n)$。
100
$n \le 1000000$
需要的区间长度是 $(u, v)$ 这个开区间的长度减去区间中比它小且被删除的数个数，实际上只需用开区间的长度减去区间中所有被删除的数个数即可。
考虑一个数，假设区间中有一个被删除且比它大，那么显然这个比它大的数所对应区间长度比原数短，这样显然不会影响答案。
对于所有被删除的位置，从大到小考虑，每次暴力找 $u$ 和 $v$，并把所有访问过的地方标记。
如果暴力的时候遇到了标记过的地方，那么原来访问到这个地方的数显然对应区间更短，此时可以不用继续找 $u$ 和 $v$ 直接考虑下一个位置，这样每个位置只会访问一次。
时间复杂度 $\mathcal O(q n)$。
B. Ernd
10
$n \le 20$
暴力枚举接的水果，线性统计答案，时间复杂度 $\mathcal O(2^n n)$。
在 DFS 过程中计算贡献优化到 $\mathcal O(2^n)$。
20
$n \le 1000$
定义“段”为满足对于其中任意相邻元素 $i$ 和 $i + 1$ ，满足接到第 $i$ 个水果后可以接到第 $i + 1$ 个水果的极长子区间。
考虑暴力 DP，定义 $f_i$ 为以第 $i$ 个水果结尾的接水果序列的最大得分，那么有：
\[f_i = \max(f_i, f_j + 1 \vert \text{接到第} j \text{个水果后可以接到第} i \text{个水果}) \tag{1}\] \[f_i = \max(f_i, f_j - 1 + (i - j + 1)^2 \vert \text{第} i \text{个水果和第} j \text{个水果属于同一段}) \tag{2}\]枚举 $j$ 进行转移，时间复杂度 $\mathcal O(n^2)$。
40
$n \le 5 \times 10^5$
答案不超过 $\mathcal 10^4$
考虑优化第一部分转移。
将水果放到二维平面上，第 $i$ 个水果变成一个坐标为 $(a_i, b_i)$ 的点，容易发现能接到的其他果子都在这个点 $[45^\circ, 135^\circ]$ 范围的方向上。
旋转坐标系，将每个点变为 $(b_i - a_i, b_i + a_i)$，那么能接到的其他果子都在这个点的右上方。
这样就转化为一个二维偏序问题，用树状数组维护上升子序列即可。
答案不超过 $10^4$，这意味着任意一段的长度都不会超过 $\sqrt{10^4} = 100$，于是第二部分暴力转移。
时间复杂度 $\mathcal O(n \log n + 100\times n)$。
100
$n \le 5 \times 10^5$
考虑优化第二部分转移。
一段内的元素在按照 $b_i - a_i$ 排序后可能不连续，但相对顺序不会改变，因此不用担心转移顺序的问题。
每段之间转移彼此独立，考虑对于每段内部分别计算。
观察转移方程 $f_i = \max \{f_j - 1 + (i - j + 1)^2 \}$，设 $P = f_j - 1 + (i - j + 1)^2$，那么有 $(f_j + j^2 - 2j) = 2i \times j + (P - i^2 - 2i)$。
这个式子可以斜率优化，将每个决策点 $j$ 化为平面上的点 $(j, f_j + j^2 - 2j) ，维护上凸壳即可。
注意维护的是上凸壳而查询斜率 $2i$ 随 $i$ 单调递增，因此需要用一个栈而不是队列来维护这个凸包，当然二分斜率也是完全可以的。
时间复杂度 $\mathcal O(n \log n)$。
考虑用另一种方法优化第二部分转移。
观察到对于决策点 $j \lt k$，随着 $i$ 的增大，$(i - j + 1)^2$ 的增长速率永远大于 $(i - k + 1)^2$ 的增长速率，这意味着一旦某一时刻 $f_j - 1 + (i - j + 1)^2 \gt f_k - 1 + (i - k + 1)^2$，那么决策点 $k$ 将会永远不可能成为最优决策点，可以删除。
由此发现了决策单调性，利用单调栈 + 二分的方法维护有效决策点，时间复杂度 $\mathcal O(n\log n)$。
C. Sanrd
50
$r \le 3 \times 10^{10}, r - l \le 10^7$
题目所要求即为 $[l, r]$ 的次大质因子之和，其中次大质因子定义为可重集的次大。
最简单的方法是将每个数质因子分解，质因子总个数是 $\mathcal O((r - l) \log r)$ 的。
预处理 $\sqrt r$ 以内的质数，考虑使用埃氏筛法进行分解，设当前质数为 $p$，那么范围内第一个被 $p$ 整除的数为 $\lceil \frac{l}{p} \rceil p$，筛法消耗的时间和质因子总个数是相同的。
时间复杂度 $\mathcal O(\sqrt{r} + (r - l) \log r)$。