← 返回题目列表

Codeforces · 1571/J

J. 两条铁路

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

Berland有$$$n$$$个城市,它们由两条铁路连接——主铁路和辅助铁路。每个城市有两个火车站,一个连接主干铁路(称为主站),另一个连接辅助铁路。

铁路的结构相同。主要铁路由 $$$n-1$$$ 铁路段组成;第 $$$i$$$ 铁路段将 $$$i$$$ 城市的主站与 $$$i+1$$$ 城市的主站连接起来。同样,辅助铁路由 $$$n-1$$$ 铁路段组成;第$$$i$$$铁路段连接城市$$$i$$$辅助站与城市$$$i+1$$$辅助站。

这些铁路用于将不同的货物和资源从一个城市转移到另一个城市。能源部特别有兴趣利用这些铁路来运输煤炭。

该部估计了铁路的以下能力:

- 对于[1, n-1]$$$中的每$$$i,每天最多可以将$$$a_i$$$吨煤炭从主站$$$i$$$转移到主站$$$i+1$$$(仅在这个方向);
- 对于[1, n-1]$$$中的每$$$i,每天最多可以将$$$b_i$$$吨煤炭从辅助站$$$i$$$转移到辅助站$$$i+1$$$(仅在这个方向);
- 对于[1, n]$$$中的每$$$i,每天最多可以将$$$c_i$$$吨煤炭从主站$$$i$$$转移到辅助站$$$i$$$,或者反向转移。

为了分析整个铁路网的容量,该部需要一个能够处理和回答以下格式查询的软件:

- 计算每天可以从主站 $$$l_i$$$ 转移到主站 $$$r_i$$$ 的最大煤炭吨数。

您的任务是实现该软件。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 城市数量。

第二行包含 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$)。

第三行包含 $$$n-1$$$ 整数 $$$b_1, b_2, \dots, b_{n-1}$$$ ($$$1 \le b_i \le 10^9$$$)。

第四行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_{n}$$$ ($$$1 \le c_i \le 10^9$$$)。

第五行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 查询数。

接下来是 $$$q$$$ 行,第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — 第 $$$i$$$ 查询的参数。

输出

打印 $$$q$$$ 整数,其中第 $$$i$$$ 个整数应该是第 $$$i$$$ 个查询的答案,i。 e.每天可以从主站 $$$l_i$$$ 转移到主站 $$$r_i$$$ 的最大煤炭吨数。

示例

输入 #1

5
3 4 7 4
8 5 3 5
10 5 3 4 10
4
1 4
1 2
3 4
2 4

输出 #1

9 8 10 9