526互联

CodeForces 1919F2 Wine Factory (Hard Version)

发布时间 2024-01-09 21:18:51作者: zltzlt

洛谷传送门

CF 传送门

题目看着感觉很像最大流，不妨建模，\(S \to i\)，容量为 \(a_i\)；\(i \to T\)，容量为 \(b_i\)；\(i \to i + 1\)，容量为 \(c_i\)。答案是这个图的最大流。

考虑最大流转最小割。观察到 \(S \to i\) 和 \(i \to T\) 的边恰好被割掉一条。因为不可能都不被割，\(S, T\) 不能同时和 \(i\) 连通。如果 \(S, i\) 连通就割 \(i \to T\)，否则割 \(S \to i\)。

这样如果割了 \(i \to T\) 和 \(S \to i + 1\)，也要割掉 \(i \to i + 1\) 的边。所以实际上是一个动态 dp。

考虑线段树维护，\([l, r]\) 对应的结点维护 \(f_{0/1, 0/1}\) 表示当 \(l\) 是割到 \(S\) 还是到 \(T\) 的边，\(r\) 是割到 \(S\) 还是到 \(T\) 的边的边权最小值。那么合并两儿子时如果是 \(f_{\ast, 1}\) 和 \(f_{0, \ast}\) 合并，那么费用再加 \(c_{mid}\)。

时间复杂度 \(O(n + m \log n)\)。

code 
// Problem: F2. Wine Factory (Hard Version)
// Contest: Codeforces - Hello 2024
// URL: https://codeforces.com/contest/1919/problem/F2
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 500100;

ll n, m, a[maxn], b[maxn], c[maxn], f[maxn << 2][2][2];

void pushup(int x, int l, int r) {
	int mid = (l + r) >> 1;
	mems(f[x], 0x3f);
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				for (int l = 0; l < 2; ++l) {
					f[x][i][l] = min(f[x][i][l], f[x << 1][i][j] + f[x << 1 | 1][k][l] + (j == 1 && k == 0 ? c[mid] : 0));
				}
			}
		}
	}
}

void build(int rt, int l, int r) {
	if (l == r) {
		f[rt][0][0] = a[l];
		f[rt][1][1] = b[l];
		f[rt][0][1] = f[rt][1][0] = 4e18;
		return;
	}
	int mid = (l + r) >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt, l, r);
}

void update(int rt, int l, int r, int x) {
	if (l == r) {
		f[rt][0][0] = a[l];
		f[rt][1][1] = b[l];
		return;
	}
	int mid = (l + r) >> 1;
	(x <= mid) ? update(rt << 1, l, mid, x) : update(rt << 1 | 1, mid + 1, r, x);
	pushup(rt, l, r);
}

void solve() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &b[i]);
	}
	for (int i = 1; i < n; ++i) {
		scanf("%lld", &c[i]);
	}
	build(1, 1, n);
	while (m--) {
		ll p, x, y, z;
		scanf("%lld%lld%lld%lld", &p, &x, &y, &z);
		a[p] = x;
		b[p] = y;
		c[p] = z;
		update(1, 1, n, p);
		printf("%lld\n", min({f[1][0][0], f[1][0][1], f[1][1][0], f[1][1][1]}));
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}