526互联

题解 CF903G【Yet Another Maxflow Problem】

发布时间 2023-10-25 10:49:15作者: rui_er

加边 \(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;
}