Yet Another Maxflow Problem

题意翻译

一张图分为两部分，左右都有 $n$ 个节点，$A_i\rightarrow A_{i+1}$ 连边，$B_i\rightarrow B_{i+1}$ 连边，容量给出。 有 $m$ 对$A_i\rightarrow B_j$有边，容量给出。 你需要先求出原图从 $A_1$ 到 $B_n$ 的最大流，然后有 $q$ 次操作，每次操作给出 $i$，先修改 $A_i\rightarrow A_{i+1}$ 的边的容量，然后询问从 $A_1$ 到 $B_n$ 的最大流。 $2\leq n,m\leq 2\times 10^5$，容量$\ \leq 10^9$。

题目描述

In this problem you will have to deal with a very special network. The network consists of two parts: part $ A $ and part $ B $ . Each part consists of $ n $ vertices; $ i $ -th vertex of part $ A $ is denoted as $ A_{i} $ , and $ i $ -th vertex of part $ B $ is denoted as $ B_{i} $ . For each index $ i $ ( $ 1<=i<n $ ) there is a directed edge from vertex $ A_{i} $ to vertex $ A_{i+1} $ , and from $ B_{i} $ to $ B_{i+1} $ , respectively. Capacities of these edges are given in the input. Also there might be several directed edges going from part $ A $ to part $ B $ (but never from $ B $ to $ A $ ). You have to calculate the [maximum flow value](https://en.wikipedia.org/wiki/Maximum_flow_problem) from $ A_{1} $ to $ B_{n} $ in this network. Capacities of edges connecting $ A_{i} $ to $ A_{i+1} $ might sometimes change, and you also have to maintain the maximum flow value after these changes. Apart from that, the network is fixed (there are no changes in part $ B $ , no changes of edges going from $ A $ to $ B $ , and no edge insertions or deletions). Take a look at the example and the notes to understand the structure of the network better.

输入输出格式

输入格式

The first line contains three integer numbers $ n $ , $ m $ and $ q $ ( $ 2<=n,m<=2·10^{5} $ , $ 0<=q<=2·10^{5} $ ) — the number of vertices in each part, the number of edges going from $ A $ to $ B $ and the number of changes, respectively. Then $ n-1 $ lines follow, $ i $ -th line contains two integers $ x_{i} $ and $ y_{i} $ denoting that the edge from $ A_{i} $ to $ A_{i+1} $ has capacity $ x_{i} $ and the edge from $ B_{i} $ to $ B_{i+1} $ has capacity $ y_{i} $ ( $ 1<=x_{i},y_{i}<=10^{9} $ ). Then $ m $ lines follow, describing the edges from $ A $ to $ B $ . Each line contains three integers $ x $ , $ y $ and $ z $ denoting an edge from $ A_{x} $ to $ B_{y} $ with capacity $ z $ ( $ 1<=x,y<=n $ , $ 1<=z<=10^{9} $ ). There might be multiple edges from $ A_{x} $ to $ B_{y} $ . And then $ q $ lines follow, describing a sequence of changes to the network. $ i $ -th line contains two integers $ v_{i} $ and $ w_{i} $ , denoting that the capacity of the edge from $ A_{vi} $ to $ A_{vi}+1 $ is set to $ w_{i} $ ( $ 1<=v_{i}<n $ , $ 1<=w_{i}<=10^{9} $ ).

输出格式

Firstly, print the maximum flow value in the original network. Then print $ q $ integers, $ i $ -th of them must be equal to the maximum flow value after $ i $ -th change.

输入输出样例

输入样例 #1

4 3 2
1 2
3 4
5 6
2 2 7
1 4 8
4 3 9
1 100
2 100

输出样例 #1

9
14
14

说明

This is the original network in the example: 

题意翻译

一张图分为两部分，左右都有 $n$ 个节点，$A_i\rightarrow A_{i+1}$ 连边，$B_i\rightarrow B_{i+1}$ 连边，容量给出。 有 $m$ 对$A_i\rightarrow B_j$有边，容量给出。 你需要先求出原图从 $A_1$ 到 $B_n$ 的最大流，然后有 $q$ 次操作，每次操作给出 $i$，先修改 $A_i\rightarrow A_{i+1}$ 的边的容量，然后询问从 $A_1$ 到 $B_n$ 的最大流。 $2\leq n,m\leq 2\times 10^5$，容量$\ \leq 10^9$。