题目大意
给一个图，可分为两部分，每部分有n个点，左边为A，右边为B。Ai向Ai+1连一条有向边，Bi向Bi+1连一条有向边，并给定m条从A到B的有向边。每条边都给定容量。多次询问，修改一条边的容量，然后求出A1到Bn的最大流。
数据范围
2≤n,m≤2×105，流量<=109。
解析
看上去似乎是一道网络流题，但只要加以分析，就会发现网络流在这道题上并没有什么用。
首先最大流等于最小割，那么就把原题转化为求最小割。可以发现，A集合和B集合中每个都最多只用删一条边。那么，如何删除两个集合之间的边呢？稍加分析就可以得到：如果删去的边是(Ai,Ai+1)和(Bj,Bj+1)，那么需要删去的中间的边(Ak,Bk)一定要满足Ak<=Ai且Bk>=Bj+1。
由此，只需要枚举删去哪一条A中的边，然后用线段树区间加的形式维护最小割。将得到的所有答案再用一棵线段树维护，改变边权就是在这棵线段树上单点修改。
还需要注意A不删边和B不删边的情况。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
#define N 200002
using namespace std;
struct SegmentTree{
int dat,add;
}t[N*4],t1[N*4];
struct point{
int x,y,w;
}p[N];
int n,m,q,i,a[N],b[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
int my_comp(const point &a,const point &b)
{
return a.x<b.x;
}
void update(int p)
{
t[p].dat=min(t[p*2].dat,t[p*2+1].dat);
}
void spread(int p)
{
if(t[p].add){
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p*2].dat+=t[p].add;
t[p*2+1].dat+=t[p].add;
t[p].add=0;
}
}
void build(int p,int l,int r)
{
if(l==r){
t[p].dat=b[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
update(p);
}
void change(int p,int l,int r,int ql,int qr,int x)
{
if(ql<=l&&r<=qr){
t[p].dat+=x;
t[p].add+=x;
return;
}
int mid=(l+r)/2;
spread(p);
if(ql<=mid) change(p*2,l,mid,ql,qr,x);
if(qr>mid) change(p*2+1,mid+1,r,ql,qr,x);
update(p);
}
void change1(int p,int l,int r,int x,int v)
{
if(l==r){
t1[p].dat+=v;
return;
}
int mid=(l+r)/2;
if(x<=mid) change1(p*2,l,mid,x,v);
else change1(p*2+1,mid+1,r,x,v);
t1[p].dat=min(t1[p*2].dat,t1[p*2+1].dat);
}
signed main()
{
n=read();m=read();q=read();
for(i=1;i<n;i++) a[i]=read(),b[i]=read();
for(i=1;i<=m;i++) p[i].x=read(),p[i].y=read(),p[i].w=read();
sort(p+1,p+m+1,my_comp);
build(1,1,n);
int pos=1;
for(i=1;i<=n;i++){
while(p[pos].x<=i&&pos<=m){
if(p[pos].y>1) change(1,1,n,1,p[pos].y-1,p[pos].w);
change(1,1,n,n,n,p[pos].w);
pos++;
}
change1(1,1,n,i,a[i]+t[1].dat);
}
printf("%lld
",t1[1].dat);
for(i=1;i<=q;i++){
int x=read(),y=read();
change1(1,1,n,x,y-a[x]);
printf("%lld
",t1[1].dat);
a[x]=y;
}
return 0;
}