加边 \(A_n\stackrel{0}{\to}A_{n+1}\),\(B_0\stackrel{0}{\to}B_1\)。称形如 \(A_i\to A_{i+1}\) 的边为左部边,形如 \(B_j\to B_{j+1}\) 的边为右部边,形如 \(A_i\to B_j\) 的边为中间边。
根据最大流最小割定理,将最大流问题转化为最小割问题求解。显然,至少存在一组最小割,包含恰好一条左部边、恰好一条右部边和若干条中间边。
设割了左部边 \(A_i\to A_{i+1}\)、右部边 \(B_j\to B_{j+1}\),则割掉的中间边一定是 \(A_u\to B_v\),其中 \(u\le i\land v > j\)。设此时割掉的所有中间边的容量和为 \(c_{i,j}\),则答案为 \(\min\limits_i\left\{a_i+\min\limits_j\left\{b_j+c_{i,j}\right\}\right\}\)。设 \(p_i=\min\limits_j\left\{b_j+c_{i,j}\right\}\),答案即为 \(\min\limits_i\left\{a_i+p_i\right\}\)。
初始时 \(p_i\) 可通过扫描线求出,由于修改操作是对 \(a_i\) 的单点改,再使用线段树维护单点改、区间 \(\min\) 即可。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const ll N = 2e5 + 5;
ll n, m, q, a[N], b[N], p[N];
vector<tuple<ll, ll>> e[N];
struct SegmentTree {
ll val[N << 2], tag[N << 2];
#define lc(u) (u << 1)
#define rc(u) (u << 1 | 1)
void pushup(ll u) {
val[u] = min(val[lc(u)], val[rc(u)]);
}
void pushdown(ll u) {
if(!tag[u]) return;
tag[lc(u)] += tag[u];
val[lc(u)] += tag[u];
tag[rc(u)] += tag[u];
val[rc(u)] += tag[u];
tag[u] = 0;
}
void build(ll* a, ll u, ll l, ll r) {
tag[u] = 0;
if(l == r) {
val[u] = a[l];
return;
}
ll mid = (l + r) >> 1;
build(a, lc(u), l, mid);
build(a, rc(u), mid + 1, r);
pushup(u);
}
void modify(ll u, ll l, ll r, ll ql, ll qr, ll k) {
if(ql <= l && r <= qr) {
tag[u] += k;
val[u] += k;
return;
}
pushdown(u);
ll mid = (l + r) >> 1;
if(ql <= mid) modify(lc(u), l, mid, ql, qr, k);
if(qr > mid) modify(rc(u), mid + 1, r, ql, qr, k);
pushup(u);
}
void clear(ll u, ll l, ll r) {
tag[u] = val[u] = 0;
if(l == r) return;
ll mid = (l + r) >> 1;
clear(lc(u), l, mid);
clear(rc(u), mid + 1, r);
}
#undef lc
#undef rc
}sgt;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
rep(u, 1, n - 1) cin >> a[u] >> b[u + 1];
rep(i, 1, m) {
ll u, v, w;
cin >> u >> v >> w;
e[u].emplace_back(v + 1, w);
}
sgt.build(b, 1, 1, n);
rep(u, 1, n) {
for(auto [v, w] : e[u]) {
sgt.modify(1, 1, n, 1, v - 1, w);
}
p[u] = a[u] + sgt.val[1];
}
sgt.build(p, 1, 1, n);
cout << sgt.val[1] << endl;
while(q--) {
ll u, w;
cin >> u >> w;
sgt.modify(1, 1, n, u, u, -a[u]);
a[u] = w;
sgt.modify(1, 1, n, u, u, +a[u]);
cout << sgt.val[1] << endl;
}
return 0;
}
- 题解 Another Maxflow Problem 903G题解another maxflow problem 题解permutation another problem 题解another problem 1870e 题解counting another problem 题解another algebra problem 题解minimization another problem 题解inversions another problem permutation codeforces another problem another problem range query permutation another problem 1858c