双一道数学题
1795MiB
·
·
个人记录
双一道数学题 & Account
给定一个长为 n 的序列 a_i, 定义一次摸牌为拿走尚存的编号最小的数, 摸到第 i 张牌会获得额外 a_i 的摸牌次数.
定义一个回合为首先摸 m 张牌, 然后根据额外的摸牌次数继续摸牌, 直到次数耗尽后弃掉所有牌. 若整个序列被摸完了, 则将所有被弃掉的牌还原到序列中.
定义一个回合能爽摸为, 开始后能一次性摸完所有 n 张牌并不弃牌 (即此时至少还要有 1 次机会). q 次单点修改, 同时询问需要开始多少次才能第一次爽摸.
相较于原题不用判断序列中是否至少有两个 > 0 的数, 这是简单的.
---
题目相当于在环上摸牌. 将序列复制一遍接在后面, 设前缀和为 $s_i$.
考虑从 $l$ 开始摸 $m$ 张牌, 在不弃牌的情况下, 最远能摸到的位置 $r$. 则此时能获得的摸牌次数为 $s_r - s_{l-1} + m$. 由于需要摸 $r - l + 1$ 张牌, 则有 $s_r - s_{l-1} + m > r - l + 1$. 因为中途不能断, 所以对于每个 $l \le i \le r$, 都要有 $s_i - s_{l-1} + m > i - l + 1$.
设 $t_i = s_i - i$. 条件变为对于每个 $l \le i \le r$ 有 $t_i - t_{l-1} + m > 0$, 即 $\min_{l \le i \le r} \{t_i\} > t_{l-1} - m$.
设 $p$ 对所有 $0 \le i \le n - 1$ 满足 $t_p > t_i$ 或 $t_p = t_i$ 且 $p<i$, 即最靠前的最小值 (注意范围).
当 $r - l + 1 = n$ 时, 条件为 $\min_{l \le i \le l + n - 1} \{t_i\} > t_{l-1} - m$. 取 $i = l + n - 1$, 则存在一个开始位置使得该回合能爽摸, 当且仅当 $t_n + m > 0$, 且此时从 $p + 1$ 开始一定能爽摸.
<details><summary>Proof</summary>
> 充分性显然, 现证明必要性, 也即证明从 $p + 1$ 开始能爽摸.
>
> 将式子拆分为 $\min_{p + 1 \le i \le n - 1} \{t_i\} > t_{p} - m$ 和 $\min_{n \le i \le p + n} \{t_i\} > t_{p} - m$.
>
> 由于 $t_p$ 为最靠前的最小值, $m > 0$, 则前一半显然成立.
>
> 后一半转化为 $\min_{0 \le i \le p} \{t_i\} > t_{p} - m - t_n$, 由于 $t_p$ 为最靠前的最小值, $t_n + m > 0$, 则后一半同样成立.
</details>
在 $t_n + m > 0$ 的情况下, 从 $q + 1 \space (q < p)$ 开始若能摸到第 $p$ 张牌且不弃牌, 则从 $q + 1$ 开始能爽摸.
<details><summary>Proof</summary>
> 需要证明 $\min_{p + 1 \le i \le n - 1} \{t_i\} > t_q - m$ 和 $\min_{n \le i \le q + n} \{t_i\} > t_q - m$.
>
> 由于 $t_p > t_q - m$, $t_p$ 为最靠前的最小值, 则前面的条件成立.
>
> 考虑归纳证明后面的条件. 当 $m = 1$ 时, 能摸到 $p$ 且不弃牌就可以当作从 $p + 1$ 开始摸且初始有一次机会, 故成立. 现假设对于 $m - 1$ 成立, 证明其对 $m$ 成立.
>
> 考虑将 $a_{q+2}$ 加上 $a_{q+1}$, 同时将 $a_{q+1}$ 变为 0. **假设这对 $p$ 的位置没有影响.** 则相当于从 $q + 2$ 开始, 初始摸 $m - 1$ 张牌, 能够摸到 $p$ 且不弃牌. 故初始摸 $m - 1$ 张牌时从 $q + 2$ 开始能爽摸, 则原序列从 $q + 1$ 开始初始摸 $m$ 张牌能爽摸.
>
> 现在证明这一操作对 $p$ 的位置没有影响. 事实上这一操作对 $t$ 的影响仅仅是 $t_{q+1} \leftarrow t_q - 1$. 故只需证明原序列 $t_q - 1 > t_p$. 由于 $t_p < t_q$, 则只需证明 $t_q - t_p \neq 1$.
>
> 现在假设 $t_q = t_p + 1$, 则由于 $t_p$ 为最靠前的最小值, 对于 $0 \le i \le p - 1$, 有 $t_i > t_p$ 即 $t_i \ge t_q$. 又由于 $q < p$, 则 $i$ 的范围可缩成 $0 \le i \le q$. 将需要证明的条件转化为 $\min_{0 \le i \le q} \{t_i\} > t_q - m - t_n$, 进一步转化为 $t_q > t_q - m - t_n$ 即 $t_n + m > 0$. 故原命题得证.
</details>
故只需要计算第几个回合能够摸到第 $p$ 张牌即可. 考虑一对极长的 $l, r$ (从 $l$ 开始不能爽摸) 满足 $\min_{l \le i \le r} \{t_i\} > t_{l-1} - m$, 则有 $t_{r+1} - t_{l-1} = m$. 由于从 $l$ 开始摸需要摸到 $r + 1$ 才会把牌全弃掉, 则相当于每让 $t$ 值下降 $m$ 就会弃牌一次. 由于 $t_0 = 0$, 则答案为 $\lfloor \frac{-t_p}{m} \rfloor + 1$.
总结, 若 $t_n + m \le 0$ (原题还要或上 只有 0 或 1 个 $\ge 1$ 的数) 则永远无法爽摸. 否则开始爽摸的回合为
$$\lfloor \frac{-\min_{i=0}^{n-1} \{t_i\}}{m} \rfloor + 1$$
.
线段树维护 $t_i$, 时间复杂度 $O((n + q) \log n)$.