← 返回题目列表

Codeforces · 1682/F

F. 最小费用最大流?

中文机器翻译题面 查看原题

给定两个整数数组 $$$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<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$$$ 的最大流量的最小成本。

您将收到两个整数 $$$l$$$ 和 $$$r$$$ 形式的 $$$q$$$ 查询。您必须计算每个查询的子数组 $$$a[l:r]$$$ 的成本,模 $$$10^9 + 7$$$。

如果您不知道最大流量的最小成本意味着什么,请阅读此处。

输入

输入的第一行包含两个整数 $$$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 \le a_2 \ldots \le 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$$$。

输出

对于每个查询 $$$l_i$$$, $$$r_i$$$ — 打印子数组 $$$a[l_i:r_i]$$$ 模 $$$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

注意

在第一个查询中,最大可能流量为 $$$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$$$。

在第三个查询中,流网络显示在左侧,容量写在边缘上,成本写在括号中。右图显示了最佳配置中通过每个边缘的流量。

在第四个查询中,流网络看起来像 –

在配置中实现了最小成本最大流量 –

上述网络中的最大流量为 4,该流量的最小成本为 15。