MCMF?
Description
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.
题面翻译
给你两个整数序列 和 且 。数组 保证非降。
一个子序列 的贡献定义如下。
- 如果 ，那么代价就没有（不会出现此类询问，就是说询问中 保证 ）。
- 此外
- 建一个有 个顶点的二分图，从 到 编号， 的顶点在左边， 的顶点在右边。对于每个 ，若 ， 且 ，则建一条从 到 的边，容量无限，费用为 。
- 再添加源 和汇 。
- 对于每个 ，若 且 ，则建一条从 到 的边，费用为 ，容量为 。
- 对于每个 ，若 且 ，则建一条从 到 的边，费用为 ，容量为 。
- 的贡献就是从 到 的 。
次查询，每次给出两个整数 和 ，求出 的贡献对 取模的结果。
Input
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$.
Output
For each query $l_i$, $r_i$ — print the cost of subarray $a[l_i:r_i]$ modulo $10^9 + 7$.
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
2
0
9
15
Note
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.
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.
相关
在下列比赛中: