CF802O April Fools' Problem (hard)

题意

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

题解

显然可以费用流解决

考虑优化费用流

引理

初始不含负圈的图在费用流的增广过程中不会出现负圈

根据引理得，每次增广的增广路都是一条形如 的路径，一共增广 次

设 表示在残流网络上 点向 的流量，则一条增广路合法当且仅当 这两条边有流量且满足下列两个条件之一：

尝试用线段树来模拟这一过程，对于每一个区间 ，维护 的最小值 ， 的最小值 ，从 到 有流量的最小 ，从 到 有流量的最小 ，从左到右的最小费用流 ，从右到左的最小费用流 ，从 到 的流量

每找到一条增广路，在线段树上更新流量并把 设为

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

发现 的值总是 ，于是使 ， 和 取整个区间每条边的流量都减去 之后的值，这样不影响区间 的答案，而且区间修改时只需要更新

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

细节详见代码

每次增广的时间复杂度可以做到 ，总时间复杂度为

代码 codeforces submission 143973639