题解：AT_arc168_f [ARC168F] Up-Down Queries

masterhuang · 2025-06-11 23:12:50 · 题解

有长为 N 的操作序列 x = (x_1, x_2, \dots, x_N)，对 f(x) 定义如下：

有长为 M 初始全 0 的序列 y，对于 i = 1, 2, \dots, N 依次进行如下操作。

• \forall j\le x_i,y_j\gets \max(y_j-1,0)
• \forall j>x_i,y_j\gets y_j+1

现在给出初始的操作序列 $x$，有 $Q$ 次修改操作，将 $x_i$ 修改为 $k$，每次操作后输出当前的 $f(x)$。 $1\le N,M,Q\le 2.5\times 10^5,1\le x_i,k\le M$。

这篇主要讲如何自然转换模拟费用流。

• 可以发现一次操作相当于先对 x_i < j \le m 的 a_j 加上 2，再对全局做 a_i = \max(0, a_i - 1) 的操作。

记 a_0 = 0，则容易发现整个操作的过程中，a_i​ 一定单调不降。

于是差分，令 d=a_i-a_{i-1}，则 ans=\sum d_i(m+1-i)。

这启发我们每次给可重集加入 d_i 个 m+1-i，最终要求 S 集合内所有数的和。

• 考虑 +2，相当于 d_{x_i+1} 加 2，于是相当于往 S 加入两个 m-x_i​。

• 考虑 -1，由于钦定 a_0 始终为 0，于是相当于第一个非 0 的 d_i 减 1，考虑 d 以及加入的过程，发现相当于删除集合内最大值！

于是转化要维护如下问题：

初始有空可重集，每次加两个 m-x_i，删除集合内最大值，最终求集合内数的和。

考虑经典 trick，把删除最大值变成删除任意数，最终求最小可能集合内数的和。

此时就很好建立费用流了（源汇为 S,T，括号内前者表示流量，后者表示费用）：

其中 i\to j 的边表示一个数在它加入的时刻后被删除，需要有桥梁连过去。

而这类边显然能拆为 (i\to i+1,\infty,0)。

然后考虑模拟这个费用流。

显然我们找到一个合法的最大流，然后不断找环增广。

把初始 x 看成从 0 开始修改。

对于修改 x，考虑一定是增广包含 x 的环。