【CF802O】April Fools' Problem (hard) 题解 （线段树模拟费用流）

线段树模拟费用流。

LG传送门。

Solution

Part 1

根据题面，显然想到此题是费用流。建图方式亦是显然：

• \(S\rightarrow i\)，流量为 \(1\)，费用为 \(a_i\)；
• \(i\rightarrow T_0\)，流量为 \(1\)，费用为 \(b_i\)；
• \(i\rightarrow i+1\)，流量为 \(\inf\)，费用为 \(0\)；
• \(T_0\rightarrow T_1\)，流量为 \(k\)，费用为 \(0\)。

观察数据，知道直接跑费用流肯定会起飞。所以我们选择模拟费用流。

Part 2

不难抓住题目条件的特性：第 \(i\) 天经过第一次处理后的东西，第二次处理的时间必定在时刻 \(i\) 之后，不能在它之前。这种特性与括号序列所具有的是相同的。

具体地，记“第一次处理”为 \(+1\)（等价于左括号），“第二次处理”为 \(-1\)（等价于右括号）。并现有一前缀数组 \(S\)，其长度为 \(n\)。若第 \(i\) 天选择第一次处理，则 \(S_i + 1\)；若选择第二次处理，则 \(S_i-1\)。与括号序列同理，这个前缀数组 \(S\) 的特点是：每一项权值都是非负数，且 \(S_n=0\)。

进而，我们现在的目标转化为：在括号序列合法的前提下，每次放入一左一右两个括号，重复 \(k\) 次，并使最终总代价最少。每次一并放两个括号，一正一负，不会改变 \(S_n\) 的值，\(S_n\) 一直为 \(0\)。

Part 3

假设将左括号放在第 \(i\) 位，右括号放在第 \(j\) 位。不难得出，每次放置只有两种情况：\(i\leq j\) 或 \(i > j\)。形象些，即是 ..(..).. 与 ..)..(..。

最直接的方式就是线段树动态维护两个序列的最小值，每次取最小值即可。这种方式对第一种情况是适用的。

但是因为括号序列前缀数组的特殊限制，对于第二种情况，需要满足前提条件：对于 \(x \in [j, i)\)，\(S_x > 0\)。

而我们使用线段树动态维护的，是对于区间 \([l,r]\)，代价最小且合法的两个数对，分别对应第一种情况以及第二种情况里的 \(i\) 和 \(j\)。此次代价即是两种情况中代价较小的一个。

如何维护第二种情况？如果直接维护权值是否为 \(0\)，未免太过麻烦，可能超时。所以我们不妨转化一下，使 \(a_0=b_0=\inf\)，那么对于 \(S_0\) 而言，必定恒为 \(0\)。故我们线段树维护的范围是 \([0,n]\)，且 \(t_1.min\)（即整个 \(S\) 序列的最小值）恒为 \(0\)。此时，满足第二种情况限制的数对，它所构成的区间，只需要保证，该区间内每个权值都严格大于整个区间的最小值。相比前者而言，它显然好维护些。

故，对于某一区间 \([l,r]\)，我们需要维护：

• \(ma\) 与 \(mb\)：满足下标在 \([l,r]\) 范围内，\(a[ma]\) 与 \(b[mb]\) 分别是各自序列中的最小值；
• \(la\) 与 \(lb\)：仅针对情况二，维护当前区间满足情况二限制的前缀 \([l,la)\) 与 \([lb,r]\)，辅助情况二求解；
• \(mn\)：下标在 \([l,r]\) 内，\(S\) 序列中的项的最小值；
• \(va\)：当前区间对于情况一的答案（一数对）；
• \(vb\)：当前区间对于情况二的答案（一数对，且考虑情况二的特殊限制）；
• \(vc\)：当前区间对于情况二的临时答案（一数对，且不考虑情况二的特殊限制）。

然后区间合并时，以上变量之间的合并差不多是基本的常见操作，\(vb\) 的合并稍复杂，详析见代码注释。

Part 4

时复 \(\mathcal{\text{O}}(n+k\log n)\)。

另：此做法可求出 \(k\in [1,n]\) 时的任一答案。

Code

内附有注释。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define ls (x<<1)
#define rs (x<<1|1)
const int maxn = 5e5 + 5, inf = 0x3f3f3f3f;
int n, k, a[maxn], b[maxn];
ll ans;
struct node{int x, y;};
struct tree{
	int ma, mb, la, lb, mn, tg;  
	node va, vb, vc;
}t[maxn << 2];
inline bool operator <(node x, node y){
	return a[x.x] + b[x.y] < a[y.x] + b[y.y];
} 
inline tree operator +(tree x, tree y){
	tree z; z.tg = 0;
	if(a[x.ma] < a[y.ma]) z.ma = x.ma; else z.ma = y.ma;
	if(b[x.mb] < b[y.mb]) z.mb = x.mb; else z.mb = y.mb;
	z.mn = min(x.mn, y.mn);//以上三者直接取最小 
	z.va = min((node){x.ma, y.mb}, min(x.va, y.va));
	z.vc = min((node){y.ma, x.mb}, min(x.vc, y.vc));//在没有特殊限制时，两区间合并可产生新的、符合条件的数对 
	z.vb = min(x.vb, y.vb);
	if(x.mn > y.mn){
	//此时，x所代表的区间内的所有数 都严格大于合并后区间最小值，所以x区间内的数可直接取最小 
		z.vb = min(z.vb, min((node){y.la, x.mb}, x.vc));
		z.la = (a[x.ma] < a[y.la] ? x.ma : y.la), z.lb = y.lb;
		/*z.la=y.la等价于这个前缀直接涵盖了x区间，并与y区间的la前缀接上了*/
	} else if(y.mn > x.mn){
		z.vb = min(z.vb, min((node){y.ma, x.lb}, y.vc));
		z.la = x.la, z.lb = (b[y.mb] < b[x.lb] ? y.mb : x.lb);
	} else{ z.la = x.la, z.lb = y.lb;
		z.vb = min(z.vb, (node){y.la, x.lb});//直接合并前后缀 
	} return z;
}

inline void psd(int x){
	if(!t[x].tg) return;
	t[ls].tg += t[x].tg, t[ls].mn += t[x].tg;
	t[rs].tg += t[x].tg, t[rs].mn += t[x].tg;
	t[x].tg = 0;
}
inline void psp(int x){ t[x] = t[ls] + t[rs];}
inline void build(int x, int l, int r){
	if(l == r) return 
		t[x] = (tree){l, l, l, 0, 0, 0, (node){l, l}, (node){0, 0}, (node){l, l}}, void();
	int mid = (l + r) >> 1;
	build(ls, l, mid), build(rs, mid + 1, r), psp(x);
}
inline void updt1(int x, int l, int r, int p){
	if(l == r) return;
	int mid = l + r >> 1; psd(x);
	if(p <= mid) updt1(ls, l, mid, p); else updt1(rs, mid + 1, r, p);
	psp(x);
}
inline void updt2(int x, int l, int r, int L, int R, int p){
	if(l > R or L > r) return;
	if(L <= l and r <= R) {t[x].tg += p, t[x].mn += p; return;}
	int mid = (l + r) >> 1; psd(x);
	updt2(ls, l, mid, L, R, p), updt2(rs, mid + 1, r, L, R, p);
	psp(x);
}

int main(){
	scanf("%d%d", &n, &k); 
	rep(i, 1, n) scanf("%d", &a[i]); rep(i, 1, n) scanf("%d", &b[i]);
	a[0] = b[0] = inf; build(1, 0, n);
	while(k--){ int x, y, p;
		if(t[1].va < t[1].vb) x = t[1].va.x, y = t[1].va.y, p = 1;
		else x = t[1].vb.x, y = t[1].vb.y, p = -1;
		ans += a[x] + b[y]; a[x] = b[y] = inf;
		updt1(1, 0, n, x), updt1(1, 0, n, y);
		updt2(1, 0, n, min(x, y), max(x, y) - 1, p);
	} printf("%lld\n", ans);
	return 0;
} 

Reference

• CF802O April Fools' Problem (hard) 题解，by KaisuoShutong.
• 题解 CF802O April Fools' Problem, by gxy001.
• 模拟费用流小记，by command_block.