CF1768F 题解

题意

给定长度为 \(n\) 的序列 \(a\)，求序列 \(f\)，满足：

\[f_i=
\begin{equation}
\begin{cases}
0&(i=1)\\
\min\limits_{j=1}^{i-1}\min\limits_{k=j}^ia_k\times(i-j)^2 &(i>1)
\end{cases}
\end{equation}
\]

\(2\le n\le 4\times10^5,1\le a_i\le n\)。

这种样式看起来很适合斜率优化或四边形不等式优化。但尝试后不可行。注意到 \(a_i\le n\) 的条件，尝试从值域下手（根号分治）。

显然转移点 \(j\) 满足 \(i-j\le\frac{n}{\min_{k=j}^ia_k}\)。则若 \(\min_{k=j}^ia_k>\sqrt n\)，\(i-j<\sqrt n\)。于是以下考虑 \(\min_{k=j}^ia_k\le\sqrt n\)。

给出一个结论，若 \(\exist t\in(i,j),a_t=\min_{k=j}^ia_k\)，则 \(i\) 必不为转移点。证明显然。则若 \(\min_{k=j}^{i-1}a_k=\min_{k=j}^ia_k\)，仅有 \(\sqrt n\) 个可能的 \(j\)。

那么仅剩 \(\min_{k=j}^{i-1}a_k>a_i\) 的情况。利用笛卡尔树易证共有 \(n\sqrt n\) 种，均摊 \(\sqrt n\)。于是此题得解。