Description：

给一个 $2\times n$ 个节点的图，其中 $n$ 个在左边，称为 $A$ ，另外 $n$ 个在右边，称为 $B$ ，每个 $A_i,B_i$ 向 $A_{i+1},B_{i+1}$ 连边，边有不同权值， $A$ 和 $B$ 之间有一些边，支持修改 $A_i$ 到 $A_{i+1}$ 的边，多次询问 $A_1$ 到 $B_n$ 的最大流。

$n,m,q\le 200000$

Solution：

首先肯定不可能真求最大流，由最大流 $=$ 最小割得只要找到一个权值最小的割集使得删掉这些边后 $A_1$ 和 $B_n$ 不连通即可，发现一定是在 $A$ 和 $B$ 中各割掉一条边，并割掉从 $A_g$ 之前的点出发连向 $B_g$ 之后的点的边，发现只会对 $A$ 修改，所以和每个 $A_k$ 对应的 $B_k$ 永远不变，考虑先提前把它求出来，依次考虑 $A$ 中的所有点 $A_i$ 并割掉边 $A_i\to A_{i+1}$ ，发现 $A$ 每向后挪一个点，从 $A_i$ 出发的边必须被割掉。设这条边为 $A_i\to B_j$ ，那么所有 $B_j$ 之前的点 $B_x$ 要想作为最终和 $A_i$ 一同割掉的边，就必须把 $A_i\to B_j$ 割掉，于是 $B$ 的一个前缀需要加上这条边边权，区间加，区间取 $min$ 用线段树第 $i$ 个位置维护割掉边 $B_{i-1}\to B_i$ 的花费（第 $1$ 个位置代表， $B$ 中一个都不割）， $A$ 一个一个往后走，每次加入从 $A_i$ 出发的边即可。

最后把所有 $A$ 放入一个可删堆中，修改直接删除 $+$ 插入即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 200010

#define INF 0x3f3f3f3f3f3f3f3f

int a[MAXN],b[MAXN];

struct edge

{

	int to,nxt,f;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].f = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

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

struct node

{

	int lc,rc;

	long long minv,tag;

	node(){lc = rc = 0;minv = tag = 0ll;} 

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void pushup(int rt)

{

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].minv = (long long)b[l];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	pushup(rt);

	return;

}

void pushdown(int rt)

{

	t[t[rt].lc].tag += t[rt].tag;

	t[t[rt].rc].tag += t[rt].tag;

	t[t[rt].lc].minv += t[rt].tag;

	t[t[rt].rc].minv += t[rt].tag;

	t[rt].tag = 0;

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		t[rt].tag += (long long)k;

		t[rt].minv += (long long)k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	pushup(rt);

	return;

}

long long query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].minv;

	long long res = INF;

	pushdown(rt);

	if(L <= mid)res = min(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = min(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

long long res[MAXN];

typedef long long ll;

struct heap

{

	priority_queue<ll,vector<ll>,greater<ll> > add;

	priority_queue<ll,vector<ll>,greater<ll> > del;

	void init()

	{

		while(!add.empty())add.pop();

		while(!del.empty())del.pop();

		return;

	}

	void insert(ll k)

	{

		add.push(k);

		return;

	}

	void remove(ll k)

	{

		del.push(k);

		return;

	}

	ll top()

	{

		while(!del.empty() && del.top() == add.top())

		{

			del.pop();add.pop();

		}

		return add.top();

	}

}h;

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= n - 1;++i)

		scanf("%d%d",&a[i],&b[i + 1]);

	int x,y,z;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&x,&y,&z);

		add(x,y,z);

	}

	build(root,1,n);

	for(int k = 1;k <= n;++k)

	{

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			add(root,1,e[i].to,e[i].f,1,n);

		}

		res[k] = query(root,1,n,1,n) + a[k];

		h.insert(res[k]);

	}

	printf("%d\n",h.top());

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

	{

		scanf("%d%d",&x,&y);

		h.remove(res[x]);

		res[x] -= a[x];

		a[x] = y;

		res[x] += a[x];

		h.insert(res[x]);

		printf("%I64d\n",h.top());

	}

	return 0;

}