CF802O April Fools' Problem (hard)

题意

有 $n$ 道题，第 $i$ 天可以花费 $a_i$ 准备一道题，花费 $b_i$ 打印一道题，每天最多准备一道题，打印一道题，准备的题可以留到以后打印，求打印 $k$ 道题的最小花费.

$1\le k\le n\le 5\times10^5$

题解

显然可以费用流解决

费用流建图

考虑优化费用流

[object Promise]

根据引理得，每次增广的增广路都是一条形如 $S\rightarrow X\rightarrow Y\rightarrow T'\rightarrow T$ 的路径，一共增广 $k$ 次

设 $f_i$ 表示在残流网络上 $i+1$ 点向 $i$ 的流量，则一条增广路合法当且仅当 $S\rightarrow X,Y\rightarrow T'$ 这两条边有流量且满足下列两个条件之一：

• $X\le Y$
• $X>Y\land \min_{Y\le i<X}f_i>0$

尝试用线段树来模拟这一过程，对于每一个区间 $[l, r]$，维护 $a$ 的最小值 $\text{minA}$，$b$ 的最小值 $\text{minB}$，从 $x$ 到 $l$ 有流量的最小 $a_x$ $\text{flowA}$，从 $r+1$ 到 $x$ 有流量的最小 $b_x$ $\text{flowB}$，从左到右的最小费用流 $\text{flowLtoR}$，从右到左的最小费用流 $\text{flowRtoL}$，从 $r+1$ 到 $l$ 的流量 $\text{minFlow}$

每找到一条增广路，在线段树上更新流量并把 $a_X,b_Y$ 设为 $\text{Infinity}$

这时候发现这个做法是不可行的，因为没法对流量快速地区间修改

发现 $f_n$ 的值总是 $0$，于是使 $\text{flowA}$，$\text{flowB}$ 和 $\text{flowRtoL}$ 取整个区间每条边的流量都减去 $\text{minFlow}$之后的值，这样不影响区间 $[1, n]$ 的答案，而且区间修改时只需要更新 $\text{minFlow}$

为了方便pushup，还需要 $\text{minFlowRtoL}$ 表示假设区间内从右到左的每条边都有流量时，从右到左最小的费用

细节详见代码

每次增广的时间复杂度可以做到 $\Theta(\log n)$，总时间复杂度为 $\Theta(k\log n)$

代码 codeforces submission 143973639