Codeforces

Luogu

分析

容易发现，至多只会割掉一条 A 边和一条 B 边。我们加边 $(A_0,A_1,0)$ 和 $(B_n,B_{n+1},0)$，然后求 $A_0$ 到 $B_{n+1}$ 的最大流，就可以转化成恰好割掉一条 A 边和一条 B 边的情况了。

设割掉了 $A_i\to A_{i+1}$ 和 $B_j\to B_{j+1}$，则此时的最大流为
$$
w_{A_i,A_{i+1}}+w_{B_j,B_{j+1}}+\sum_{u\leq i,v>j}w_{A_u,B_v}
$$
显然对于每个 $i$，后面的式子的最小值是确定的，可以先用线段树预处理出来，记作 $k_i$。

然后相当于单点修改、区间求 $\min$，线段树即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,q;
ll a[N],b[N],c[N];
vector<pair<int,int> > E[N];

#define ls (o<<1)
#define rs (o<<1|1)
ll minv[N<<2],addv[N<<2];
inline void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
inline void pushdown(int o) {
    if (addv[o]) {
        addv[ls]+=addv[o],minv[ls]+=addv[o];
        addv[rs]+=addv[o],minv[rs]+=addv[o];
        addv[o]=0;
    }
}
inline void build(int o,int l,int r,ll* s) {
    addv[o]=0;
    if (l==r) { minv[o]=s[l]; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid,s),build(rs,mid+1,r,s);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { addv[o]+=w,minv[o]+=w; return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
#undef ls
#undef rs

int main() {
    n=read(),m=read(),q=read();
    for (re int i=1;i<n;++i) a[i]=read(),b[i+1]=read();
    a[n]=b[1]=0;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read()+1,w=read();
        E[u].push_back(make_pair(v,w));
    }
    build(1,1,n,b);
    for (re int i=1;i<=n;++i) {
        for (auto v:E[i]) modify(1,1,n,1,v.first,v.second);
        c[i]=minv[1];
    }
    for (re int i=1;i<=n;++i) c[i]+=a[i];
    build(1,1,n,c); printf("%lld\n",minv[1]);
    while (q--) {
        int p=read(),w=read();
        modify(1,1,n,p,p,w-a[p]),a[p]=w;
        printf("%lld\n",minv[1]);
    }
    return 0;
}