CF903G Yet Another Maxflow Problem

考虑最大流=最小割

不妨把a到a的边称为a类边，b到b的称为b类边，a到b的称为c类边。

显然，答案一定是由最多1条a和最多一条b以及一些c组成的。

只有a是会变的，也就是说每个a对应了唯一的最优的b和c。

因此可以先求一下每个a对应的最优的b和c。

分析一下可得，a，b确定后，c应该是所有满足x<a,y>b的边组成的集合。

这个二维偏序显然排序加线段树就解决了。

然后变成n个数字，支持修改某个数字，维护最小值，一个set就好了。

#include<iostream>

#include<cctype>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<ctime>

#include<set>

#include<cstdlib>

#include<algorithm>

#define N 1100000

#define L 1000000

#define eps 1e-7

#define inf 1e15+7

#define db double

#define ll long long

#define ldb long double

using namespace std;

inline ll read()

{

	char ch=0;

	ll x=0,flag=1;

	while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*flag;

}

struct lnk{ll x,y,z;}p[N];

bool cmp(lnk a,lnk b){return a.x<b.x;}

ll a[N],b[N],f[N];

struct Segment_Tree

{

	#define lson o<<1

	#define rson o<<1|1

	#define mid ((l+r)>>1)

	ll minv[N*4],addv[N*4];

	inline void pushup(ll o){minv[o]=min(minv[lson],minv[rson]);}

	inline void pushdown(ll o)

	{

		minv[lson]+=addv[o];minv[rson]+=addv[o];

		addv[lson]+=addv[o];addv[rson]+=addv[o];

		addv[o]=0;

	}

	void optadd(ll o,ll l,ll r,ll ql,ll qr,ll num)

	{

		if(ql<=l&&r<=qr){minv[o]+=num;addv[o]+=num;return;}

		pushdown(o);

		if(ql<=mid)optadd(lson,l,mid,ql,qr,num);

		if(qr>mid)optadd(rson,mid+1,r,ql,qr,num);

		pushup(o);

	}

	ll query(){return minv[1];}

}T;

multiset<ll>S;

int main()

{

	ll n=read(),m=read(),q=read();

	T.optadd(1,0,n,n,n,inf);

	for(ll i=1;i<n;i++)a[i]=read(),b[i]=read(),T.optadd(1,0,n,i,i,b[i]);

	for(ll i=1;i<=m;i++)p[i].x=read(),p[i].y=read(),p[i].z=read();

	sort(p+1,p+m+1,cmp);

	for(ll i=1,j=0;i<=n;i++)

	{

		while(j<m&&p[j+1].x<=i)j++,T.optadd(1,0,n,0,p[j].y-1,p[j].z);

		f[i]=T.query();S.insert(a[i]+f[i]);

	}

	printf("%lld\n",*(S.begin()));

	for(ll i=1;i<=q;i++)

	{

		ll x=read(),y=read();

		S.erase(S.find(a[x]+f[x]));

		a[x]=y;S.insert(a[x]+f[x]);

		printf("%lld\n",*(S.begin()));

	}

	return 0;

}