大家好这里是写题面的JRY。

最近因为种种原因，UR 跳票了半个多月的时间，不过终于，新的一场 UOJ Round 还是和大家见面啦。（在某学堂的提醒下，管理员们终于想起来还有UR这回事了...

因为写题面的人比较懒，所以这一次的标题就用了杜老师的格式:)

希望大家能够喜欢这一次的题目owo

Yist

By matthew99

算法一

直接状压每一种可能的子序列，时间复杂度$O(2 ^ npoly(n) + q)$，期望得分30分。

算法二

二分之后贪心每次删除最小的数，判断是否可行。由于删除一个数会让更大的数“更容易”被删，所以这个算法显然是正确的。

时间复杂度$O(n ^ 2\log n)$，期望得分60分。

算法三

使用平衡树等数据结构优化算法二，时间复杂度$O(qn \log ^ 2n)$，由于常数大可能较难通过90分的数据。

算法四

我们考虑到对于一个数，删除它最小需要的区间长度是多少，如果我们在序列左右都加上一个无穷小且没有被删除，考虑找到它左边没有被删除的第一个比它小的位置$u$，右边没有被删除的第一个比它小的位置$v$，那么需要的区间长度就是$(u, v)$这个开区间的长度减去这个区间中所有比它小且需要删除的数的个数。答案就是所有数对于的区间长度的最小值。

从左往右扫一遍，并用set或者什么其他数据结构维护一下，可以求出所有的$u$和$v$，然后从小到大加入，用树状数组或者什么其他数据结构维护一下即可求出区间中所有比它小且需要删除的数的个数。时间复杂度$O(qn \log n)$，期望得分90分。

算法五

算法四中提到，需要的区间长度就是$(u, v)$这个开区间的长度减去这个区间中所有比它小且需要删除的数的个数，实际上，我们只需要用开区间的长度减去这个区间中所有需要删除的数的个数即可。

考虑一个数，假设区间中有一个数需要删除且比它大，那么显然这个比它大的数所对应的区间长度比原数短，所以这样显然不会影响答案（因为我们要求的只是最小值）。

所以我们只要求出$u$和$v$即可。

这样很多劣于线性的算法都能AC，这里列举几个：

维护A的单调栈，并在上面二分，由于常数小可以AC。

用ST表加上二分，然后加上一些优化$O(1)$去除一些显然不能更新答案的位置，也可以AC。

从大到小加数，所有被删除的和已经被加入的未被删除的位置记为1，其他位置记为0，则显然$u$和$v$分别就是左边和右边的第一个0，用并查集很好维护，如果不计读入的话时间复杂度为$O(qn \log n)$或者$O(qn \alpha(n))$。

算法六：

为了避免成为辣鸡卡常出题人，接下来我来讲讲线性做法，我的程序可以在时限的大约三分之一内出解。

其实很简单，对于所有被删除的位置，从大到小，每次暴力找$u$和$v$，并把所有访问过的地方标记，如果暴力的时候遇到了标记过的地方，那么可以发现原来访问到这个地方的数显然对应的区间更短，所以这个时候可以不用继续找$u$和$v$，直接考虑下一个位置即可，这样每个位置只会访问一次，若不考虑读入，则时间复杂度$O(qn)$，期望得分100分。

题外话：

我看到开场就有几个人交了正解的第一步：只找最大的一个数暴力找$u$和$v$更新答案，首先我样例是随机的所以你们很容易通过，其次我第一个点也是随机的所以你们也能过第一个点的十分，其他点应该都是过不了的，我想说的是你们就不会认真分析一下问题再提交么，实际上如果你们只找最大的几个更新答案也是很难有很多分的。考虑一下有两个阶梯，一个阶梯就是左右两边都是很小的未被删除的数，中间是比两边大的被删除的数和比被中间所有所有被删除的数都要大的未删除的数，那么如果第一个阶梯的数比第二个阶梯的数大而且第一个区间更短，那么更新答案的应该是第二个阶梯中的最大值，这样前面很多很多个数对应的区间都不是答案。

Ernd

By PoPoQQQ

因为A题和C题难度偏高所以出了道简单题平衡一下难度

ctb上瘾的出题人

算法一

对于subtask1，$n\leq20$。

暴力枚举接哪些水果，线性统计得分，时间复杂度 $O(n\times2^n)$。

用DFS的方式可以将复杂度降低至 $O(2^n)$。

期望得分 $10$ 分。

并没有什么卵用的算法。

算法二

对于subtask2，$n\leq1000$

我们定义“段”为满足对于其中任意相邻元素 $i$ 和 $i+1$ ，满足接到第 $i$ 个水果后可以接到第 $i+1$ 个水果的极长子区间。

考虑暴力dp，定义 $f_i$ 为以第 $i$ 个水果结尾的接水果序列的最大总得分，那么有：

$f_i=\max(f_i,f_j+1|\text{ 接到第 }j\text{ 个水果后可以接到第 }i\text{ 个水果})$

$f_i=\max(f_i,f_j-1+(i-j+1)^2|\text{ 第 }i\text{ 个水果和第 }j\text{ 个水果属于同一段})$

枚举 $j$ 进行转移，时间复杂度 $O(n^2)$，期望得分 $20$ 分。

算法三

我们考虑如何优化第一部分转移。

我们将水果都放在二维平面上，第 $i$ 个水果变成一个坐标为 $(a_i,b_i)$ 的点，那么容易发现，接到一个果子后，能接到的其他果子都在这个点的 $[45^\circ,135^\circ]$ 范围的方向上。

旋转坐标系，将每个点变为 $(b_i-a_i,b_i+a_i)$，那么接到一个果子后，能接到的其他果子都在这个点的右上方。

问题变成了一个二维偏序问题，用树状数组维护上升子序列即可。

观察subtask4，$n\leq5\times10^5$，答案不超过$10^4$，这意味着任意一段的长度都不会超过 $\sqrt{10^4}=100$。

第一部分转移使用算法三，第二部分转移暴力，时间复杂度 $O(n\log n+100\times n)$ ，期望得分 $40$ 分。

算法四

现在开始考虑如何优化第二部分转移。

注意到一段内的元素在按照 $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$ 单调递增，因此我们需要用一个栈而不是队列来维护这个凸包。

当然你要二分斜率也是完全可以的。

时间复杂度 $O(n\log n)$，期望可以通过全部测试点拿到 $100$ 分。

算法五

考虑用另一种方法优化第二部分转移。

观察到对于决策点 $j< k$，随着 $i$ 的增大，$(i-j+1)^2$ 的增长速率永远大于 $(i-k+1)^2$ 的增长速率，这意味着一旦某一时刻 $f_j-1+(i-j+1)^2 > f_k-1+(i-k+1)^2$，那么决策点 $k$ 将会永远不可能成为最优决策点，决策点 $k$ 可以删除。

由此我们发现了决策单调性，利用单调栈+二分的方法维护有效决策点，时间复杂度 $O(n\log n)$，期望可以通过全部测试点拿到 $100$ 分。

什么你问我subtask3是干嘛的？

照顾常数写残党/数据结构爆搞党/乱搞党。

以上。

Sanrd

By Stilwell

算法一

容易发现我们需要求的是$l\sim r$这段数的次大质因子之和，其中次大质因子定义为可重集的次大。

一个最简单的方法是将每个数都质因子分解，对于前50\%的数据，$r-l\leq 10^7$，这一段数的质因子总个数是$O((r-l)\log r)$的。

预处理出$\sqrt{r}$范围内的质数，考虑使用埃氏筛法进行分解，设当前质数为$p$，那么范围内第一个被$p$整除的数为$\lceil\frac{l}{p}\rceil p$，筛法消耗的时间和质因子总个数是相同的。

时间复杂度$O(\sqrt{r}+(r-l)\log r)$，期望得分50分。

算法二

原问题等价于求$1\sim n$的次大质因子之和。

考虑用$[1,n]$范围内的所有数做一个乘积背包，设$f[i]$表示现在乘积为$i$的数的最大质因子之和，升序枚举质因子可以保证当前质因子是转移后的最大质因子，转移前的最大质因子就是需要求的次大质因子，背包生成的每个数都是不重复的，所以可以直接计入答案。

容易发现$f[i]$的可能取值只有两种，0或$i$的最大质因子，取决于当前枚举的质数能不能组成$i$。这样表示状态明显非常浪费，可以尝试优化。

对于一个数$x(x\leq n)$，$x$的次大质因子一定$\leq \sqrt{n}$，所以$>\sqrt{n}$的质数我们可以考虑批量转移。

对于一个状态$i$，在背包时还能转移的质数需要$\leq\lfloor\frac{n}{i}\rfloor$，不妨直接用$\left\lfloor\frac{n}{i}\right\rfloor$来表示状态。

设$g[j]$表示$\lfloor\frac{n}{i}\rfloor=j$的数的最大质因子之和，由于$\lfloor\frac{n}{i}\rfloor$的取值只有$O(\sqrt{n})$种，所以状态数缩减为$O(\sqrt{n})$，原先$i\rightarrow ip$的转移变化为$j\rightarrow \lfloor\frac{j}{p}\rfloor$。

那么现在问题就转化为这样两部分：

1. 求$\leq\lfloor\frac{n}{i}\rfloor$且$>\sqrt{n}$的质数个数。
2. 用$\leq\sqrt{n}$的质数完成$g[j]$的背包。

先来解决第一部分，设$p_1\sim p_m$为$\leq\sqrt{n}$的质数，且$p_i < p_{i+1}$。

设$P[i][j]$为$[1,j]$ 范围内与前$i$个质数互质的数的个数，需要求的即为 $P[m][j]$。

设$l=\lfloor\frac{j}{p_i}\rfloor$，容易得到以下递推式 $$P[i][j]=P[i-1][j]-P[i-1][l]$$

递推时只需要计算$\lfloor\frac{n}{i}\rfloor$这$O(\sqrt{n})$个状态就能完成转移。

设质数密度为$O(\frac{1}{\log n})$，那么暴力递推的计算量可以估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{i}{\log i}\right)+\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{n}}{\log\sqrt{n}}\right)\thickapprox O\left(\frac{n}{\log n}\right)$$

当$p_{i+1}>j$时，一定满足$P[i][j]=1$。

所以，当${p_i}^2>j\geq p_i$时 $$P[i][j]=P[i-1][j]-1$$

因此，不必重新计算${p_i}^2>j$的情况，记录$j$最近一次被更新时的$i$的值，设为$pre_j$，在调用$P[i][j]$时，将编号$pre_j+1\sim i$间的质数计入。

考虑对于每个$\lfloor\frac{n}{i}\rfloor$计算有多少质数需要转移，计算量可估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{i}}{\log i}\right)+\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{\frac{n}{i}}}{\log\sqrt{\frac{n}{i}}}\right)$$

后半部分一定大于前半部分，故复杂度可以估计为 $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}O\left(\frac{\sqrt{\frac{n}{i}}}{\log\sqrt{\frac{n}{i}}}\right)\approx O\left(\frac{\int_0^{\sqrt{n}}\sqrt{\frac{n}{x}}\mathrm{d}x}{\log n}\right)=O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$$

完成了质数部分的计算，考虑$g[j]$部分的计算，暴力转移需要枚举每个质数再枚举每个状态，复杂度同样为$O\left(\frac{n}{\log n}\right)$。

回想前一部分是如何优化的，考虑如何省去$p^2>j=\lfloor\frac{n}{i}\rfloor$时的运算。

有$p^2>j\Rightarrow\lfloor\frac{j}p\rfloor < p\leq \sqrt{n}$，所以这些状态在以后的转移中只能再加入一个$\leq\sqrt{n}$的质数了，可以这样优化：

1. 这一部分转移不再进行。
2. 记录最后一次更新$g[j]$时的$p$，最后再计算相应的贡献。
3. 当转移到这些$g[j]$时，不更新$g[j]$，直接统计剩下还能使用的质数个数，计算相应的贡献。

优化后复杂度和第一部分一样为$O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$。

时间复杂度$O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$，期望得分100分。