QOJ8542. Add One 2 题解

zrl123456 · 2025-11-23 16:36:09 · 题解

:::::info[题目基本信息] 考察：笛卡尔树，数学，贪心（个人认为上位紫）。
题目简介：
给定序列 \{a_n\}，有一个序列 \{b_n\} 初始全为 0，你有两种操作：

• 选择一个整数 k\in[1,n]，进行操作 \forall i\in[1,k],b_i\leftarrow b_i+1，代价为 k。
• 选择一个整数 k\in[1,n]，进行操作 \forall i\in[k,n],b_i\leftarrow b_i+1，代价为 n-k+1。

问最后要使得 \forall i\in[1,n],b_i\ge a_i 的最小代价是多少。
数据范围：

• 1\le n\le 10^6
• \forall i\in[1,n],0\le a_i\le 10^9

  ::::: 从全 0 序列转化成 \{b_n\} 不方便我们研究 \{b_n\} 的性质，所以我们考虑把过程倒过来，从 \{b_n\} 转化成全 0 序列，然后将操作变为前后缀减 1。
  考虑一下差分，如果 b_i>b_{i+1}，那么我们至少要在 i 这个位置进行 b_i-b_{i+1} 次前缀减 1 操作，这时序列变成单调不递减序列，那么只需要令 b_1\ge 0 即可满足条件。
  但是我们只考虑前缀减不考虑后缀减是否有正确性？
  虽然感性理解很有正确性，但是我们还是严谨证明它。
  :::::success[证明]{open} 把上面那段文字转化成数学语言就是 \displaystyle b_1\ge\sum_{i=1}^{n-1}\max(0,b_i-b_{i+1})，类似地可以得到后缀和的式子 \displaystyle b_n\ge\sum_{i=1}^{n-1}\max(0,b_{i+1}-b_i)，这两者是否等价？
  设 b_0=b_{n+1}=inf（inf 是一个足够大的值，但不是 +\infty，否则无法比较大小），那么上述式子可以转化为 \displaystyle b_0\ge\sum_{i=0}^n\max(0,b_i-b_{i+1}) 以及 \displaystyle b_{n+1}\ge\sum_{i=0}^n\max(0,b_{i+1}-b_i)，容易发现两个等式左右两部分相等，所以这两个式子等价。
  ::::: 为方便我们将上面两式相加（其实不搞也可以推），得到：

  \sum_{i=0}^n|b_i-b_{i+1}|\le 2inf

  现在我们需要从 \{a_n\} 数组通过不断进行单点加 1 操作使得满足上面的条件，通过手玩发现减少上面的值的唯一基础操作就是通过给满足以下条件的 [l,r] 区间加 1：

• \forall i\in[l,r),a_i=a_{i+1}
• a_{l-1}>a_l\land a_r<a_{r+1}

这时，它会对上面的值贡献 2。
所以我们贪心考虑快速找到序列中的最短的极长内凹相等连续段，这个我们建出笛卡尔树，然后把每个子树按子树大小排到桶里存储它们能操作的次数，循环减少值即可。
这样我们就做完了这道题。
时空复杂度均为 \Theta(n)。

code