24.10.13

KinNa-Sky / 2024-10-14 / 原文

P3648

P3648 [APIO2014] 序列分割

李超树用多了已经不会单调队列维护斜率优化了...

首先切的顺序不影响答案。$(x + y)z + xy = x(y + z) + yz$。更多份同理。

$sum$ 表示前缀和，$suf$ 表示后缀和。设 $f_{i, j}$ 表示前 $i$ 个数切成 $j$ 份的最大值。

$f_{i, j} \gets \max_{k = 1}^{i - 1} (f_{k, j - 1} + suf_{i + 1}(sum_i - sum_k))$.

先拆柿子 $f_{i, j} - suf_{i + 1}sum_i = f_{k, j - 1} - suf_{i + 1}sum_k$.

看上去很斜率优化，~~考虑每一层维护一个李超树~~，李超树带 $\log$ 过不去。注意到 $sum$ 和 $suf$ 都单调考虑单调队列。

对于两个决策点 $k, j, k < j$，$j$ 比 $k$ 更优满足 $f_k - suf_{i + 1}sum_k < f_j - suf_{i + 1}sum_j$。

移项解得 $\dfrac{f_j - f_k}{sum_j - sum_k} > suf_{i + 1}$。$suf$ 单调递减，把 $(sum_i, f_i)$ 看成点，维护一个斜率单调减的单调队列（凸包）。

由于 $a_i$ 可能为 $0$，当 $sum_j = sum_k$ 时返回极大值。

P6302/P5468

P6302 / P5468 回家路线

以边为状态 dp。

先将边按 $p$ 排序，设 $f_i$ 表示到第 $i$ 条边，等待烦躁值的最小值。

那么枚举可以转移的边

$f_i \gets \min_j(f_j + A(p_i - q_j) ^ 2 + B(p_i - q_j) + C)$.

拆：$f_i - Ap_i^2 - Bp_i^2 - C = -2Ap_iq_j + f_j + Aq_j^2 - Bq_j$.

然后 $k < j$，$j$ 由于 $k$ 即 $-2Aq_kp_i + f_k + Aq_k^2 - Bq_k > -2Aq_jp_i + f_j + Aq_j^2 - Bq_j$，也就是 $\dfrac{(f_j + Aq_j^2 - Bq_j) - (f_k + Aq_k^2 - Bq_k)}{q_j - q_k} < 2Ap_i$。

然后可以对每个点开一个单调队列，转移边时从 $x$ 转移，存到 $y$ 的单调队列。

转移要求 $q_j \le p_i$，可以先把已转移好的边放到按 $q$ 排列的小根堆里，在处理 $i$ 之前把 $q_j < p_i$ 的边压入单调队列。

P11191

P11191 「KDOI-10」超级演出

差点场切 /kk

由于选的是一段连续区间，考虑找出序列中 $a_i$ 可以走的最大的左端点，记为 $could_i$，这样的话如果询问区间包含 $[could_i, i]$ 就可以走一个。

但是 $a_i$ 可能相同，维护 $a_i$ 上一次出现的位置记为 $lst_{a_i}$，如果 $[could_{lst_{a_i}}, lst_{a_i}]$ 和 $[could_i, i]$ 同时被包含，就会重复计算贡献，减去即可，相当于 $[could_{lst_{a_i}}, i]$ 区间会造成 $-1$ 的贡献。

区间内子区间贡献是经典离线二维数点，不多赘述。

现在讲一下如何找到 $could_i$，我们可以遍历序列时维护 $went_{x}$ 表示 $x$ 这个点能走的最大左端点，如果 $x$ 指向 $1$，那么 $went_x$ 就是 $x$ 在序列中最后出现的位置，不然 $went_x$ 就是 $x$ 指向点的 $went$ 的最大值。

此时我们意识到如果出题人放个菊花就能把这个过程卡成 $O(n^2)$，考虑使用根号分治优化。

如果一个点的出边数小于等于根号，那么每次暴力找即可。不然每个点开一个 vector 记录它出度大于根号的前驱，在更新完每个点的 $went$ 后直接对其出度大于根号的前驱进行更新。

然后这时注意 $went_x$ 由于在 $x$ 出现前被更新了，所以在 $x$ 被遍历到之前 $went_x$ 不能去更新别的点，那么出度小于根号的点暴力找的时候就去找上一次的状态来更新，即 $could_{lst_y}$。

Code