专栏文章

题解：AT_agc049_e [AGC049E] Increment Decrement

xxzy090626七里香
AT_agc049_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioqbhkn
此快照首次捕获于
2025/12/02 23:24
3 个月前
此快照最后确认于
2025/12/02 23:24
3 个月前
查看原文
铜牌题。
这个题目需要一个基本结论：通过 33 操作完成一个序列的代价是 C∑max⁡(ai−ai−1,0)C\sum \max(a_i-a_{i-1},0)。
我们可以钦定先做区间、再做单点修改。
那我们考虑先对一个序列做 dp，不妨把状态想得暴力一点，设 fi,jf_{i,j} 为当前计算了前 ii 个位置，第 jj 个位置在区间操作之后为 cic_i。
那么转移方程就是 fi,j=∣ai−j∣+min⁡k(fi−1,k+Cmax⁡(j−k,0))f_{i,j}=|a_i-j|+\min_k (f_{i-1,k}+C\max(j-k,0))。
然后我们这个地方要用 slope trick 优化了。我之前没有学过这个，所以现在学一下。
学完了。我们考虑分步进行这个转移的过程，首先进行 fi,j←min⁡(min⁡k≤jfi−1,k+C(j−k),min⁡k>jfi−1,k)f_{i,j}\leftarrow \min(\min_{k\leq j} f_{i-1,k}+C(j-k),\min_{k>j} f_{i-1,k})。
考虑对于 k>jk>j 的情况，实际上只需要考虑左半边（单调递减），发现可以全部推平为最小值；
对于 k<jk<j 的情况，我们考虑什么时候可以更新，首先显然是只有右半边需要考虑。可以先把所有 fi,jf_{i,j} 置为 fi−1,jf_{i-1,j}，然后考虑要满足 fi−1,j>fi−1,k+Cj−Ckf_{i-1,j}>f_{i-1,k}+Cj-Ck，整理一下就是 fi−1,j−Cj>fi−1,k−Ckf_{i-1,j}-Cj>f_{i-1,k}-Ck，这个可以用函数 f′(i)=f(i)−Cif^\prime(i)=f(i)-Ci 来表示，f′(i)f^\prime(i) 实质上就是原函数所有的直线斜率减少 CC，而不等式的意义是 f′(j)>f′(k)f^\prime(j)>f^\prime(k)。考虑不等式满足的条件，发现新的零点就是原来斜率为 CC 的直线的右端点，因此可以用这个零点去更新斜率 >C>C 的位置，即全部推平。至于为什么不能使用新零点左边的点来更新的原因是，我们发现左侧斜率 ≤C\leq C，而附加代价的变化率就是 CC 了，因此向左一定不优。
然后对于 ∣ai−j∣|a_i-j| 的贡献的维护就是老生常谈了，往维护的容器里塞两个 aia_i 即可。
我们注意到，根据更新操作的特点，实际上斜率总是 ∈[−1,C+1]\in [-1,C+1]。那我们考虑使用 multiset 维护斜率集合，操作可以如下刻画：
  • 预处理：加入 C+2C+2 个 00，这是因为 f0(i)=Cif_0(i)=Ci，即斜率均为 CC。
  • 对于每一轮操作，删去最大值和最小值，这是推平 −1-1 和 C+1C+1 的段。
  • 加入两个 aia_i。这是加入一个绝对值函数，表示 aia_i 处的斜率变化值为 22。
  • 计算贡献，考虑最小值的变化，也是很套路地统计原来最小值的位置和 aia_i 的最小距离，设原来斜率为 −1-1 的右端点为 pp，它在更新后斜率变为 00，因此贡献要加上 ai−pa_i-p。显然，pp 也是 multiset 里的最小值。
现在，我们可以 O(nlog⁡n)O(n\log n) 地解决这个子问题了。
考虑整个流程，即加入 C+2C+2 个 00 之后要循环做的事情：
删去最大值和最小值，加入两个 aia_i，ans←ai−min⁡ans\leftarrow a_i-\min。
考虑拆开做，首先计算 aia_i 部分的贡献系数。由于选了 aia_i 之后可以随便选，都能产生贡献，因此贡献系数为 Kn−1K^{n-1}。
考虑统计所有情况下的 pp 之和。这里就需要一些 trick 了，首先考虑从值域出发，枚举所有可能的 pp，计算最小值 ≤p\leq p 和 <p<p 的方案数的差值，就是 pp 的贡献系数。这样，就把统计的单点问题转化成区间问题了，而我们也就不关心最大值的情况了。
那我们考虑将问题进一步简化为 0101 问题，这样的好处是将 multiset 的维护转化成了单个变量（11 的个数）的维护问题了。不妨让 ai←[ai≥p]a_i\leftarrow [a_i\geq p]，这样相当于如果有 00，那么最小值 <p<p 成立。
考虑何种情况下最小值不为 00。发现每次删除最小值时都会删掉一个最初加上的 00（第一轮会删掉两个），因此 C+1C+1 轮之后如果此前全都有 ai=1a_i=1，那么在第 C+2C+2 轮时如果 ai=1a_i=1 那么本轮会出现一次这样的情况。也就是说，当出现 C+2C+2 个 ai=1a_i=1 时才能满足条件。此后如果一直满足 ai=1a_i=1 那么 11 的数量就会维持在 C+2C+2（全部为 11），于是可以据此 dp。
设 fi,jf_{i,j} 为前 ii 个位置，11 的数量为 jj，那么最小值为 11 的方案数就是 ∑i=1nKn−ifi,C+2\sum\limits_{i=1}^n K^{n-i} f_{i,C+2}；可以容斥一下，总方案数是 nKnnK^n，即每个位置都有 KnK^n 种情况产生或者不产生贡献，这样两个值相减就得到了所有位置满足最小值 <p<p 的方案数之和 ∑i=1nKn−Kn−ifi,C+2\sum\limits_{i=1}^n K^n-K^{n-i}f_{i,C+2}。
现在考虑如何转移。考虑当前的 fi,jf_{i,j} 向后进行第 i+1i+1 轮的转移，先删去最大值和最小值，即 j←j−[j>0]−[j=C+2]j\leftarrow j-[j>0]-[j=C+2]。
然后枚举可选的 KK 种 aia_i，注意它们本质的不同只在于与 pp 的关系，即有多少个当前能作为 11，剩下的作为 00。
这样，我们 dp 的复杂度就是 O(n2CK)O(n^2CK)，这也是总时间复杂度。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...