题目传送门
题目大意
给定一个网络。网络分为$A$，$B$两个部分，每边各有$n$个点。对于$A_{i} \ (1\leqslant i < n)$会向$A_{i + 1}$连一条容量为$x_{i}$的有向边，对于$B_{i} \ (1\leqslant i < n)$会向$B_{i + 1}$连一条容量为$y_{i}$的有向边。$A$和$B$之间有$m$条边，起点为$A_{u_{i}}$，终点为$B_{v_{i}}$，容量为$w_{i}$的有向边。要求支持多次修改边的容量，询问$A_{1}$到$B_{n}$的最大流。
看起来不会退流的样子，所以应该可以用数据结构乱搞搞就能做出来。于是我想了很久但仍然不会。
因为最大流的流量等于最小割的容量，所以最大流不好做的时候考虑最小割。
直接考虑最小割的求解变成了最大流，这样没有用。考虑放宽一下约束条件，找一下怎样的割集是较优的。
一些显而易见的结论：
- 假如在$A$中，割掉$A_{x}$和$A_{x + 1}$之间的有向边，那么割掉$A_{y} \ (y > x)$与$A_{y + 1}$之间的有向边是没有意义的。
- 假如在$B$中，割掉$B_{x}$和$B_{x + 1}$之间的有向边，那么割掉$B_{y} \ (y < x)$与$B_{y + 1}$之间的有向边是没有意义的。
因此，在$A, B$中至多有一条边属于割集。
假设在$A$中被割掉的边是$(A_{x}, A_{x + 1})$，在$B$中被割掉的边是$B_{y}, B_{y + 1}$，那么任意$(A_{u}, B_{v}) \ (u \leqslant x \wedge v > y)$都是属于这个割集的。
因此，割的大小可以看做三部分：在$A$中的割集大小，在$B$中的割集大小，在$A, B$间的割集大小。
由于后两部分不会改变，考虑计算出它们。
考虑在$A$中从小到大枚举$A_{x}$，表示割掉$A_{x}$和$A_{x + 1}$之间的边，如果$x = n$表示不存在这条边。
那么下面要做的事情是在$B$中找到一个最优决策点$y$，使得后两部分的和最小。
对于每加入一条在$A,B$间的边，对答案造成的影响是连续的一段。
所以我们只需要写一个支持区间加，求$[1, n]$的最小值的线段树就好了。
到此，我们完美解决这道题了吗？
不，还剩下合并两部分的答案。这个可以用一个可删堆来维护。
时间复杂度$O((n + m + q)\log n)$。
Code
/**
* Codeforces
* Problem#903G
* Accepted
* Time: 451ms
* Memory: 31200k
*/
#include <bits/stdc++.h>
#ifdef WIN32
#define Auto "%I64d"
#else
#define Auto "%lld"
#endif
using namespace std; #define ll long long typedef class SegTreeNode {
public:
ll minv, lazy;
SegTreeNode *l, *r; SegTreeNode():minv(), lazy(), l(NULL), r(NULL) { } void pushUp() {
minv = min(l->minv, r->minv);
} void pushDown() {
l->minv += lazy, r->minv += lazy;
l->lazy += lazy, r->lazy += lazy;
lazy = ;
}
}SegTreeNode; #define Limit 500000 SegTreeNode pool[Limit];
SegTreeNode* top = pool; SegTreeNode* newnode() {
return top++;
} typedef class SegTree {
public:
SegTreeNode* rt; SegTree() { }
SegTree(int n, int* ar) {
build(rt, , n, ar);
} void build(SegTreeNode*& p, int l, int r, int *ar) {
p = newnode();
if (l == r) {
p->minv = ar[l];
return;
}
int mid = (l + r) >> ;
build(p->l, l, mid, ar);
build(p->r, mid + , r, ar);
p->pushUp();
} void update(SegTreeNode*& p, int l, int r, int ql, int qr, int val) {
if (l == ql && r == qr) {
p->minv += val, p->lazy += val;
return;
}
if (p->lazy) p->pushDown();
int mid = (l + r) >> ;
if (qr <= mid)
update(p->l, l, mid, ql, qr, val);
else if (ql > mid)
update(p->r, mid + , r, ql, qr, val);
else {
update(p->l, l, mid, ql, mid, val);
update(p->r, mid + , r, mid + , qr, val);
}
p->pushUp();
}
}SegTree; #define pii pair<int, int> typedef class Heap {
public:
priority_queue<ll> que;
priority_queue<ll> del; Heap() { } void insert(ll x) {
que.push(-x);
} void remove(ll x) {
del.push(-x);
} ll top() {
while (!que.empty() && !del.empty() && que.top() == del.top())
que.pop(), del.pop();
return -que.top();
}
}Heap; int n, m, q;
int *cs1, *cs2;
vector<pii> *g;
Heap hp;
SegTree st; inline void init() {
scanf("%d%d%d", &n, &m, &q);
cs1 = new int[(n + )];
cs2 = new int[(n + )];
g = new vector<pii>[(n + )];
cs1[n] = , cs2[] = ;
for (int i = ; i < n; i++)
scanf("%d%d", cs1 + i, cs2 + i + );
for (int i = , u, v, w; i <= m; i++) {
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(pii(v, w));
}
} ll *olds;
inline void solve() {
olds = new ll[(n + )];
st = SegTree(n, cs2);
for (int i = ; i <= n; i++) {
for (int j = ; j < (signed) g[i].size(); j++)
st.update(st.rt, , n, , g[i][j].first, g[i][j].second);
hp.insert(olds[i] = cs1[i] + st.rt->minv);
// cerr << olds[i] << endl;
}
printf(Auto"\n", hp.top());
int p, nw;
while (q--) {
scanf("%d%d", &p, &nw);
hp.remove(olds[p]);
olds[p] = olds[p] - cs1[p] + nw, cs1[p] = nw;
hp.insert(olds[p]);
printf(Auto"\n", hp.top());
}
} int main() {
init();
solve();
return ;
}