CF802O April Fools' Problem (hard)

luogu $\color{deeppink}link$

CF $\color{deeppink}link$

$\texttt{wqs}$ 做法

每天可以用 $a_i$ 的时间准备一道题和用 $b_i$ 的时间打印一道已经准备过的题，求打满 $k$ 道题的最小花费。

注意到随着 $k$ 增加，答案及斜率单调增，于是可以用 $\texttt{wqs}$ 贰分。

贰分每一个题需要的额外贡献，在每一个 $a_i$ 加上他，再用 $b_i$ 去匹配前面的某一个 $a_j$，用反悔贪心即可实现。

具体的，维护一个小根堆，从 $1$ 到 $n$ 依次枚举一遍，先加入 $a_i-mid$，再用 $b_i$ 去匹配最小的 $a$，然后在堆中加入 $-b_i$ 表示反悔，但是要注意当 $b_i$ 匹配的值是正数的话是不可以进行匹配的，否则最后的 $tot$ 计数的并不是最优的，还可以减去这些正数的贡献。

复杂度是 $O(n\log n\log V)$。

线段树优化网络流做法

有一个显然的建图方式。

• $S$ 向 $i$ 连一条 $(1,a_i)$
• $i$ 向 $T'$ 连一条 $(1,b_i)$
• $i$ 向 $i+1$ 连一条 $(\inf,0)$
• $T'$ 向 $T$ 连一条 $(k,0)$

我们将一个合法的匹配方式中的 $a$ 视为 $($，$b$ 视为 $)$，这个匹配一定是合法的括号匹配。

考虑反悔机制。

插入一个 $()$，那么 $[i,j)$ 的前缀和数组 $+1$，插入一个 $)($，$[i,j)$ 减一。

可以维护以下东西：

• $mi$：区间前缀和最小值

• $val1$：$()$ 的最小值的 $(i,j)$

• $val2$：$)($ 的最小值的 $(i,j)$

• $val3$：满足区间前缀和最小值大于 $mi$ 的值最小的 $(i,j)$

然后就是一大堆东西，Immaculacy 博客。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e6;

int n,k,a[N],b[N];

struct node
{
	int val,f;
	
	friend bool operator<(node a,node b)
	{
		return a.val>b.val;
	}
};priority_queue<node>q;

main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	int l=0,r=2e9;
	while(l<=r)
	{
		while(!q.empty())q.pop();
		int mid=(l+r)>>1,res=0,num=0;
		for(int i=1;i<=n;i++)
		{
			int val=a[i]-mid;
			q.push((node){val,1});
			int p=b[i]+q.top().val;
			if(p<=0)
			{
				num+=q.top().f;res+=p;
				q.pop();q.push((node){-b[i],0});
			}
		}
		if(num==k)
		{
			cout<<res+k*mid;
			return 0;
		}
		if(num<k)l=mid+1;
		if(num>k) r=mid-1;
	}
}