309463: CF1682F. MCMF?
Memory Limit：256 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
MCMF?
题意翻译
给你两个整数序列 $a$ 和 $b(b_i \neq 0)$ 且 $|b_i| \leq 10^9$。数组 $a$ 保证非降。 一个子序列 $a[l:r]$ 的贡献定义如下。 - 如果 $sum_{j = l}^{r} b_j\neq 0$，那么代价就没有（不会出现此类询问，就是说询问中 $l, r$ 保证 $sum_{j = l}^{r} b_j = 0$ ）。 - 此外 - 建一个有 $r-l+1$ 个顶点的二分图，从 $l$ 到 $r$ 编号，$b_i \lt 0$ 的顶点在左边，$b_i \gt 0$ 的顶点在右边。对于每个 $i, j$，若 $l\le i, j\le r$，$b_i<0$ 且 $b_j>0$，则建一条从 $i$ 到 $j$ 的边，容量无限，费用为 $|a_i-a_j|$。 - 再添加源 $S$ 和汇 $T$。 - 对于每个 $i$，若 $l\le i\le r$ 且 $b_i<0$，则建一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。 - 对于每个 $i$，若 $l\le i\le r$ 且 $b_i>0$，则建一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。 - $a[l:r]$ 的贡献就是从 $S$ 到 $T$ 的 $\mathrm{MCMF}$。 $q$ 次查询，每次给出两个整数 $l$ 和 $r$，求出 $a[l:r]$ 的贡献对 $10^9 + 7$ 取模的结果。题目描述
You are given two integer arrays $ a $ and $ b $ ( $ b_i \neq 0 $ and $ |b_i| \leq 10^9 $ ). Array $ a $ is sorted in non-decreasing order. The cost of a subarray $ a[l:r] $ is defined as follows: - If $ \sum\limits_{j = l}^{r} b_j \neq 0 $ , then the cost is not defined. - Otherwise: - Construct a bipartite flow graph with $ r-l+1 $ vertices, labeled from $ l $ to $ r $ , with all vertices having $ b_i \lt 0 $ on the left and those with $ b_i \gt 0 $ on right. For each $ i, j $ such that $ l \le i, j \le r $ , $ b_i<0 $ and $ b_j>0 $ , draw an edge from $ i $ to $ j $ with infinite capacity and cost of unit flow as $ |a_i-a_j| $ . - Add two more vertices: source $ S $ and sink $ T $ . - For each $ i $ such that $ l \le i \le r $ and $ b_i<0 $ , add an edge from $ S $ to $ i $ with cost $ 0 $ and capacity $ |b_i| $ . - For each $ i $ such that $ l \le i \le r $ and $ b_i>0 $ , add an edge from $ i $ to $ T $ with cost $ 0 $ and capacity $ |b_i| $ . - The cost of the subarray is then defined as the minimum cost of maximum flow from $ S $ to $ T $ . You are given $ q $ queries in the form of two integers $ l $ and $ r $ . You have to compute the cost of subarray $ a[l:r] $ for each query, modulo $ 10^9 + 7 $ . If you don't know what the minimum cost of maximum flow means, read [here](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem).输入输出格式
输入格式
The first line of input contains two integers $ n $ and $ q $ $ (2 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 2\cdot10^5) $ — length of arrays $ a $ , $ b $ and the number of queries. The next line contains $ n $ integers $ a_1,a_2 \ldots a_n $ ( $ 0 \leq a_1 \le a_2 \ldots \le a_n \leq 10^9) $ — the array $ a $ . It is guaranteed that $ a $ is sorted in non-decreasing order. The next line contains $ n $ integers $ b_1,b_2 \ldots b_n $ $ (-10^9\leq b_i \leq 10^9, b_i \neq 0) $ — the array $ b $ . The $ i $ -th of the next $ q $ lines contains two integers $ l_i,r_i $ $ (1\leq l_i \leq r_i \leq n) $ . It is guaranteed that $ \sum\limits_{j = l_i}^{r_i} b_j = 0 $ .
输出格式
For each query $ l_i $ , $ r_i $ — print the cost of subarray $ a[l_i:r_i] $ modulo $ 10^9 + 7 $ .
输入输出样例
输入样例 #1
8 4
1 2 4 5 9 10 10 13
6 -1 1 -3 2 1 -1 1
2 3
6 7
3 5
2 6输出样例 #1
2
0
9
15说明
In the first query, the maximum possible flow is $ 1 $ i.e one unit from source to $ 2 $ , then one unit from $ 2 $ to $ 3 $ , then one unit from $ 3 $ to sink. The cost of the flow is $ 0 \cdot 1 + |2 - 4| \cdot 1 + 0 \cdot 1 = 2 $ . In the second query, the maximum possible flow is again $ 1 $ i.e from source to $ 7 $ , $ 7 $ to $ 6 $ , and $ 6 $ to sink with a cost of $ 0 \cdot |10 - 10| \cdot 1 + 0 \cdot 1 = 0 $ . In the third query, the flow network is shown on the left with capacity written over the edge and the cost written in bracket. The image on the right shows the flow through each edge in an optimal configuration.  Maximum flow is $ 3 $ with a cost of $ 0 \cdot 3 + 1 \cdot 1 + 4 \cdot 2 + 0 \cdot 1 + 0 \cdot 2 = 9 $ .In the fourth query, the flow network looks as – The minimum cost maximum flow is achieved in the configuration – The maximum flow in the above network is 4 and the minimum cost of such flow is 15.Input
题意翻译
给你两个整数序列 $a$ 和 $b(b_i \neq 0)$ 且 $|b_i| \leq 10^9$。数组 $a$ 保证非降。 一个子序列 $a[l:r]$ 的贡献定义如下。 - 如果 $sum_{j = l}^{r} b_j\neq 0$，那么代价就没有（不会出现此类询问，就是说询问中 $l, r$ 保证 $sum_{j = l}^{r} b_j = 0$ ）。 - 此外 - 建一个有 $r-l+1$ 个顶点的二分图，从 $l$ 到 $r$ 编号，$b_i \lt 0$ 的顶点在左边，$b_i \gt 0$ 的顶点在右边。对于每个 $i, j$，若 $l\le i, j\le r$，$b_i<0$ 且 $b_j>0$，则建一条从 $i$ 到 $j$ 的边，容量无限，费用为 $|a_i-a_j|$。 - 再添加源 $S$ 和汇 $T$。 - 对于每个 $i$，若 $l\le i\le r$ 且 $b_i<0$，则建一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。 - 对于每个 $i$，若 $l\le i\le r$ 且 $b_i>0$，则建一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。 - $a[l:r]$ 的贡献就是从 $S$ 到 $T$ 的 $\mathrm{MCMF}$。 $q$ 次查询，每次给出两个整数 $l$ 和 $r$，求出 $a[l:r]$ 的贡献对 $10^9 + 7$ 取模的结果。Output
**标题：MCMF?**
**题意翻译：**
给定两个整数序列 $a$ 和 $b$（$b_i \neq 0$ 且 $|b_i| \leq 10^9$），其中序列 $a$ 保证非降序。一个子序列 $a[l:r]$ 的贡献定义如下：
- 如果 $\sum_{j = l}^{r} b_j \neq 0$，那么代价未定义（在询问中不会出现此类情况，即 $l, r$ 保证 $\sum_{j = l}^{r} b_j = 0$）。
- 否则：
- 建一个有 $r-l+1$ 个顶点的二分图，顶点从 $l$ 到 $r$ 编号，$b_i < 0$ 的顶点在左边，$b_i > 0$ 的顶点在右边。对于每个 $i, j$，若 $l \le i, j \le r$，$b_i < 0$ 且 $b_j > 0$，则建一条从 $i$ 到 $j$ 的边，容量无限，费用为 $|a_i-a_j|$。
- 再添加源 $S$ 和汇 $T$。
- 对于每个 $i$，若 $l \le i \le r$ 且 $b_i < 0$，则建一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。
- 对于每个 $i$，若 $l \le i \le r$ 且 $b_i > 0$，则建一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。
- $a[l:r]$ 的贡献就是从 $S$ 到 $T$ 的**最小费用最大流**（MCMF）。
进行 $q$ 次查询，每次给出两个整数 $l$ 和 $r$，求出 $a[l:r]$ 的贡献对 $10^9 + 7$ 取模的结果。
**题目描述：**
给你两个整数数组 $a$ 和 $b$（$b_i \neq 0$ 且 $|b_i| \leq 10^9$）。数组 $a$ 是非降序的。子数组 $a[l:r]$ 的代价定义如下：
- 如果 $\sum_{j = l}^{r} b_j \neq 0$，那么代价未定义。
- 否则：
- 构造一个二分图，有 $r-l+1$ 个顶点，从 $l$ 到 $r$ 标记，所有 $b_i < 0$ 的顶点在左边，$b_i > 0$ 的顶点在右边。对于每个 $i, j$，若 $l \le i, j \le r$，$b_i < 0$ 且 $b_j > 0$，则画一条从 $i$ 到 $j$ 的边，容量无限，单位流的费用为 $|a_i-a_j|$。
- 添加两个顶点：源 $S$ 和汇 $T$。
- 对于每个 $i$，若 $l \le i \le r$ 且 $b_i < 0$，则添加一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。
- 对于每个 $i$，若 $l \le i \le r$ 且 $b_i > 0$，则添加一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。
- 子数组的代价定义为从 $S$ 到 $T$ 的最小费用最大流。
给定 $q$ 次查询，形式为两个整数 $l$ 和 $r$。对于每个查询，计算子数组 $a[l:r]$ 的代价，模 $10^9 + 7$。
如果你不知道什么是**最小费用最大流**，请阅读[这里](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem**标题：MCMF?** **题意翻译：** 给定两个整数序列 $a$ 和 $b$（$b_i \neq 0$ 且 $|b_i| \leq 10^9$），其中序列 $a$ 保证非降序。一个子序列 $a[l:r]$ 的贡献定义如下： - 如果 $\sum_{j = l}^{r} b_j \neq 0$，那么代价未定义（在询问中不会出现此类情况，即 $l, r$ 保证 $\sum_{j = l}^{r} b_j = 0$）。 - 否则： - 建一个有 $r-l+1$ 个顶点的二分图，顶点从 $l$ 到 $r$ 编号，$b_i < 0$ 的顶点在左边，$b_i > 0$ 的顶点在右边。对于每个 $i, j$，若 $l \le i, j \le r$，$b_i < 0$ 且 $b_j > 0$，则建一条从 $i$ 到 $j$ 的边，容量无限，费用为 $|a_i-a_j|$。 - 再添加源 $S$ 和汇 $T$。 - 对于每个 $i$，若 $l \le i \le r$ 且 $b_i < 0$，则建一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。 - 对于每个 $i$，若 $l \le i \le r$ 且 $b_i > 0$，则建一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。 - $a[l:r]$ 的贡献就是从 $S$ 到 $T$ 的**最小费用最大流**（MCMF）。 进行 $q$ 次查询，每次给出两个整数 $l$ 和 $r$，求出 $a[l:r]$ 的贡献对 $10^9 + 7$ 取模的结果。 **题目描述：** 给你两个整数数组 $a$ 和 $b$（$b_i \neq 0$ 且 $|b_i| \leq 10^9$）。数组 $a$ 是非降序的。子数组 $a[l:r]$ 的代价定义如下： - 如果 $\sum_{j = l}^{r} b_j \neq 0$，那么代价未定义。 - 否则： - 构造一个二分图，有 $r-l+1$ 个顶点，从 $l$ 到 $r$ 标记，所有 $b_i < 0$ 的顶点在左边，$b_i > 0$ 的顶点在右边。对于每个 $i, j$，若 $l \le i, j \le r$，$b_i < 0$ 且 $b_j > 0$，则画一条从 $i$ 到 $j$ 的边，容量无限，单位流的费用为 $|a_i-a_j|$。 - 添加两个顶点：源 $S$ 和汇 $T$。 - 对于每个 $i$，若 $l \le i \le r$ 且 $b_i < 0$，则添加一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。 - 对于每个 $i$，若 $l \le i \le r$ 且 $b_i > 0$，则添加一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。 - 子数组的代价定义为从 $S$ 到 $T$ 的最小费用最大流。 给定 $q$ 次查询，形式为两个整数 $l$ 和 $r$。对于每个查询，计算子数组 $a[l:r]$ 的代价，模 $10^9 + 7$。 如果你不知道什么是**最小费用最大流**，请阅读[这里](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem
**题意翻译：**
给定两个整数序列 $a$ 和 $b$（$b_i \neq 0$ 且 $|b_i| \leq 10^9$），其中序列 $a$ 保证非降序。一个子序列 $a[l:r]$ 的贡献定义如下：
- 如果 $\sum_{j = l}^{r} b_j \neq 0$，那么代价未定义（在询问中不会出现此类情况，即 $l, r$ 保证 $\sum_{j = l}^{r} b_j = 0$）。
- 否则：
- 建一个有 $r-l+1$ 个顶点的二分图，顶点从 $l$ 到 $r$ 编号，$b_i < 0$ 的顶点在左边，$b_i > 0$ 的顶点在右边。对于每个 $i, j$，若 $l \le i, j \le r$，$b_i < 0$ 且 $b_j > 0$，则建一条从 $i$ 到 $j$ 的边，容量无限，费用为 $|a_i-a_j|$。
- 再添加源 $S$ 和汇 $T$。
- 对于每个 $i$，若 $l \le i \le r$ 且 $b_i < 0$，则建一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。
- 对于每个 $i$，若 $l \le i \le r$ 且 $b_i > 0$，则建一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。
- $a[l:r]$ 的贡献就是从 $S$ 到 $T$ 的**最小费用最大流**（MCMF）。
进行 $q$ 次查询，每次给出两个整数 $l$ 和 $r$，求出 $a[l:r]$ 的贡献对 $10^9 + 7$ 取模的结果。
**题目描述：**
给你两个整数数组 $a$ 和 $b$（$b_i \neq 0$ 且 $|b_i| \leq 10^9$）。数组 $a$ 是非降序的。子数组 $a[l:r]$ 的代价定义如下：
- 如果 $\sum_{j = l}^{r} b_j \neq 0$，那么代价未定义。
- 否则：
- 构造一个二分图，有 $r-l+1$ 个顶点，从 $l$ 到 $r$ 标记，所有 $b_i < 0$ 的顶点在左边，$b_i > 0$ 的顶点在右边。对于每个 $i, j$，若 $l \le i, j \le r$，$b_i < 0$ 且 $b_j > 0$，则画一条从 $i$ 到 $j$ 的边，容量无限，单位流的费用为 $|a_i-a_j|$。
- 添加两个顶点：源 $S$ 和汇 $T$。
- 对于每个 $i$，若 $l \le i \le r$ 且 $b_i < 0$，则添加一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。
- 对于每个 $i$，若 $l \le i \le r$ 且 $b_i > 0$，则添加一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。
- 子数组的代价定义为从 $S$ 到 $T$ 的最小费用最大流。
给定 $q$ 次查询，形式为两个整数 $l$ 和 $r$。对于每个查询，计算子数组 $a[l:r]$ 的代价，模 $10^9 + 7$。
如果你不知道什么是**最小费用最大流**，请阅读[这里](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem**标题：MCMF?** **题意翻译：** 给定两个整数序列 $a$ 和 $b$（$b_i \neq 0$ 且 $|b_i| \leq 10^9$），其中序列 $a$ 保证非降序。一个子序列 $a[l:r]$ 的贡献定义如下： - 如果 $\sum_{j = l}^{r} b_j \neq 0$，那么代价未定义（在询问中不会出现此类情况，即 $l, r$ 保证 $\sum_{j = l}^{r} b_j = 0$）。 - 否则： - 建一个有 $r-l+1$ 个顶点的二分图，顶点从 $l$ 到 $r$ 编号，$b_i < 0$ 的顶点在左边，$b_i > 0$ 的顶点在右边。对于每个 $i, j$，若 $l \le i, j \le r$，$b_i < 0$ 且 $b_j > 0$，则建一条从 $i$ 到 $j$ 的边，容量无限，费用为 $|a_i-a_j|$。 - 再添加源 $S$ 和汇 $T$。 - 对于每个 $i$，若 $l \le i \le r$ 且 $b_i < 0$，则建一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。 - 对于每个 $i$，若 $l \le i \le r$ 且 $b_i > 0$，则建一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。 - $a[l:r]$ 的贡献就是从 $S$ 到 $T$ 的**最小费用最大流**（MCMF）。 进行 $q$ 次查询，每次给出两个整数 $l$ 和 $r$，求出 $a[l:r]$ 的贡献对 $10^9 + 7$ 取模的结果。 **题目描述：** 给你两个整数数组 $a$ 和 $b$（$b_i \neq 0$ 且 $|b_i| \leq 10^9$）。数组 $a$ 是非降序的。子数组 $a[l:r]$ 的代价定义如下： - 如果 $\sum_{j = l}^{r} b_j \neq 0$，那么代价未定义。 - 否则： - 构造一个二分图，有 $r-l+1$ 个顶点，从 $l$ 到 $r$ 标记，所有 $b_i < 0$ 的顶点在左边，$b_i > 0$ 的顶点在右边。对于每个 $i, j$，若 $l \le i, j \le r$，$b_i < 0$ 且 $b_j > 0$，则画一条从 $i$ 到 $j$ 的边，容量无限，单位流的费用为 $|a_i-a_j|$。 - 添加两个顶点：源 $S$ 和汇 $T$。 - 对于每个 $i$，若 $l \le i \le r$ 且 $b_i < 0$，则添加一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$。 - 对于每个 $i$，若 $l \le i \le r$ 且 $b_i > 0$，则添加一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$。 - 子数组的代价定义为从 $S$ 到 $T$ 的最小费用最大流。 给定 $q$ 次查询，形式为两个整数 $l$ 和 $r$。对于每个查询，计算子数组 $a[l:r]$ 的代价，模 $10^9 + 7$。 如果你不知道什么是**最小费用最大流**，请阅读[这里](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem