CF1682F.MCMF?

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 \lt 0$ and $b_j \gt 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 \lt 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 \gt 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.

给你两个整数数组 $a$ 和 $b$（其中 $b_i \neq 0$ 且 $|b_i| \leq 10^9$）。数组 $a$ 按非递减顺序排序。

子数组 $a[l:r]$ 的代价定义如下：

• 若 $\sum\limits_{j = l}^{r} b_j \neq 0$，则该代价未定义；

• 否则：

  • 构造一个二分流图，包含 $r-l+1$ 个顶点，编号从 $l$ 到 $r$：所有满足 $b_i \lt 0$ 的顶点置于左侧，所有满足 $b_i \gt 0$ 的顶点置于右侧；对任意 $i, j$ 满足 $l \le i, j \le r$、$b_i \lt 0$ 且 $b_j \gt 0$，添加一条从 $i$ 到 $j$ 的有向边，容量为无穷大，单位流量的费用为 $|a_i-a_j|$；
  • 再添加两个顶点：源点 $S$ 和汇点 $T$；
  • 对每个满足 $l \le i \le r$ 且 $b_i \lt 0$ 的 $i$，添加一条从 $S$ 到 $i$ 的边，费用为 $0$，容量为 $|b_i|$；
  • 对每个满足 $l \le i \le r$ 且 $b_i \gt 0$ 的 $i$，添加一条从 $i$ 到 $T$ 的边，费用为 $0$，容量为 $|b_i|$；
  • 该子数组的代价即为从 $S$ 到 $T$ 的最大流的最小费用。

你将收到 $q$ 个查询，每个查询由两个整数 $l$ 和 $r$ 组成。对每个查询，你需要计算子数组 $a[l:r]$ 的代价，并对 $10^9 + 7$ 取模。

若你不了解“最大流的最小费用”的含义，请参阅此处。

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$.

输入的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 2\cdot 10^5$，$1 \leq q \leq 2\cdot10^5$）——分别表示数组 $a$、$b$ 的长度以及查询次数。

下一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 10^9$）——即数组 $a$。保证 $a$ 是按非递减顺序排序的。

再下一行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$-10^9 \leq b_i \leq 10^9$，且 $b_i \neq 0$）——即数组 $b$。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i,r_i$（$1 \leq l_i \leq r_i \leq n$）。保证 $\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$.

对于每个查询 $l_i$、$r_i$，输出子数组 $a[l_i:r_i]$ 的代价对 $10^9 + 7$ 取模的结果。

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.

在第一次查询中，最大可能流为 $1$，即：$1$ 个单位从源点流向节点 $2$，再从节点 $2$ 流向节点 $3$，最后从节点 $3$ 流向汇点。该流的费用为 $0 \cdot 1 + |2 - 4| \cdot 1 + 0 \cdot 1 = 2$。

在第二次查询中，最大可能流仍为 $1$，即：从源点流向节点 $7$，再从节点 $7$ 流向节点 $6$，最后从节点 $6$ 流向汇点，其费用为 $0 \cdot |10 - 10| \cdot 1 + 0 \cdot 1 = 0$。

在第三次查询中，左侧展示了流网络图，其中每条边上的数值表示容量，括号内数值表示单位流量费用。右侧图像展示了最优配置下各条边上的实际流量。

该网络的最大流为 $3$，对应最小费用为 $0 \cdot 3 + 1 \cdot 1 + 4 \cdot 2 + 0 \cdot 1 + 0 \cdot 2 = 9$。

在第四次查询中，流网络结构如下所示：

最小费用最大流在如下配置中实现：

上述网络中的最大流为 $4$，且该最大流对应的最小费用为 $15$。