D
Easy Version
枚举最小值\(v\)（\(0\leq v\leq a_1\)），然后我们希望最小化最大值。
也就是说，对\(\forall i\)，我们在满足\(\lfloor \frac{a_i}{p_i} \rfloor \geq v\)的前提下，使\(\lfloor \frac{a_i}{p_i} \rfloor\)最小，即使\(p_i\)最大，可得\(p_i=\min(k,\lfloor\frac{a_i}{v}\rfloor)\)。
令\(M(v)=\max(p_i)\)，则\(ans=\min(M(v)-v)\)。
Hard Version
Solution 1
每次暴力计算\(M\)太慢了，我们考虑\(a_i\)会对\(M\)造成怎样的影响。
设\(\lfloor \frac{a_i}{p_i}\rfloor\)值域为\(\left\{s_1,s_2,\cdots s_x \right\}\)，可以证明\(x\)为\(\mathcal{O}(\sqrt{a_i})\)。
- 若\(v \leq s_1\)则\(M(v)\)至少为\(s_1\)。
- 当\(s_1 < v \leq s_2\)时，\(M(v)\)至少为\(s_2\)。
- 当\(s_2<v\leq s_3\)时，\(M(v)\)至少为\(s_3\)。
以此类推，当\(s_i<v\leq s_{i+1}\)时，\(M(v)\)至少为\(s_{i+1}\)。
也就是说\(M(v)\)取决于\(v\)落在\(\lfloor \frac{a_i}{p_i} \rfloor\)值域的哪两个端点，\(M(v)\)就是这些右端点的最大值。
倒过来想，对于每个\(s_i\)，我们希望把所有大于\(s_i\)，且小于等于\(s_{i+1}\)的\(v\)的\(M(v)\)更新为\(\max(M(v),s_{i+1})\)。
这部分不需要数据结构，只需一个辅助数组\(m\)，对于每个\(s_i\)，另\(m_{s_i+1}=\max(m_{s_i+1},s_{i+1})\)，则\(M(v)=\max_{i=0}^{v}m(i)\)。
Solution 2
现在考虑枚举\(v\)作为最大值，我们希望最大化最小值。
考虑每个\(a_i\)。
- 若\(a_i\leq v\)，我们令\(p_i=1\)。
- 若\(v<a_i\leq2v+1\)，我们不能使\(\lfloor \frac{a_i}{p_i}\rfloor\)超过\(v\)，又希望其最大，可令\(p_i=2\)。
- 若\(2v+1<a_i\leq 3v+2\)，令\(p_i=3\)。
以此类推，对\(uv+u-1<a_i\leq (u+1)v+u\)，我们令\(p_i=u+1\)。
右端点\((u+1)v+u\)是使\(\lfloor \frac{a_i}{u+1}\rfloor \leq v\)的临界，左端点\(uv+u-1\)是使\(\lfloor\frac{a_i}{u}>v \rfloor\)的边界。
也就是说，对于\(0\leq u < k\)，我们找到第一个大于\(uv+u-1\)的\(a_i\)，如果\(a_i\leq(u+1)v+u\)，则更新最小值\(mn=\min(mn,\lfloor\frac{a_i}{u+1}\rfloor)\)。
具体而言，用双指针维护\(nxt\)数组，\(nxt_i\)表示\(a\)中第一个大于等于\(i\)的位置。
从\(0\)到\(k-1\)枚举\(u\)，更新最小值\(mn=min(mn,\lfloor \frac{a_{nxt_{uv+u}}}{u+1}\rfloor)\)
枚举\(u\)的过程中若发现\(uv\geq a_n\)，就退出循环。
注意如果\(\lfloor\frac{a_n}{k} \rfloor\geq v+1\)，即\(a_n\geq k(v+1)\)，则\(v\)一定不是最大值，不合法。
时间复杂度\(\mathcal{O}(\sum_{i=1}^{a_n}\frac{a_n}{i})=\mathcal{O}(a_n\log(a_n))\)。
E
首先有三个小结论。
- 若\(l=r\)，则答案为\(0\)。
- 设\(f_i\)为询问\([i-1.i]\)的答案，则\([l,r]\)的答案为\(\max_{i=l+1}^{r}f_i\) 。
- 对于两个点\(x,y\)，使它们联通的最小的\(k\)，是原图最小生成树上两点间边权的最大值。
证明第二个（第一个显然）：
令\(k=\)\(\max_{i=l+1}^{r}f_i\)。
首先答案一定不超过\(k\)，因为用\(1 \sim k\)即可连接\(l\sim r\)的任意两点。
若答案为\(k'(k'<k)\)，则一定有\(f_i \leq k'\)，因为根据定义，\(i-1\)可以通过\(1\sim k'\)的边到达\(i\)。
\(f_i \leq k'<k\)，但又一定有一个\(f_i\)的值为\(k\)，矛盾。
证明第三个：
考虑\(kruscal\)的过程，若加入一条边\(k+1\)，发现\(x,y\)已联通，则这条边一定无用（不改变任意两点的连通性）。
建出最小生成树后对于每个\(i\geq 2\)，询问\(i-1\)到\(i\)路径边权最大值即\(f(i)\)，可以用倍增实现。
对于\([l,r]\)，询问\([l+1,r]\)中\(f_i\)的最大值，就是\(RMQ\)，同样可以用倍增，也可以用线段树。
标签：lfloor,frac,max,最大值,rfloor,leq,CF1706D From： https://www.cnblogs.com/cooltyl/p/16879229.html