← 返回题目列表

Codeforces · 2193/C

C. 替换并求和

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

今天,KQ 在圣杯学院进行考试。一位严厉的老师布置了一个KQ无法解决的任务。他得到了两个长度为 $$$n$$$ 的数组 $$$a$$$ 和 $$$b$$$。 KQ 可以对数组执行以下操作:

  • 选择索引 $$$i$$$ ($$$1\le i\lt n$$$) 并将 $$$a_i$$$ 替换为 $$$a_{i+1}$$$。
  • 选择索引 $$$i$$$ ($$$1\le i\le n$$$) 并将 $$$a_i$$$ 替换为 $$$b_i$$$。
现在他有 $$$q$$$ 查询。每个查询由两个数字 $$$l$$$ 和 $$$r$$$ 描述。他的任务是找到每个查询的总和 $$$(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$$$ 的最大值,如果他可以对数组的任何元素执行任意数量的操作。由于他对此不够熟练,因此他请求您的帮助。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ $$$(1\le n, q\le 2 \cdot 10^5)$$$。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2,...,a_n$$$ $$$(1\le a_i\le 10^4)$$$。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2,...,b_n$$$ $$$(1\le b_i\le 10^4)$$$。

以下 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ $$$(1\le l\le r\le n)$$$。

保证所有测试用例中 $$$n$$$ 的值之和以及 $$$q$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出以空格分隔的 $$$q$$$ 数字 — 总和的最大值 $$$(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$$$。

示例

输入
复制

4
3 1
3 2 1
1 2 3
1 3
1 1
1
2
1 1
3 2
6 7 5
9 6 8
1 2
2 3
4 3
4 3 2 1
5 1 3 1
1 2
2 4
3 4

输出
复制

9
2
17 16
8 7 4

注意

考虑第一个测试用例。将 $$$a_3$$$ 替换为 $$$b_3$$$,$$$a = [3, 2, 3]$$$。将 $$$a_2$$$ 替换为 $$$a_3$$$,$$$a = [3, 3, 3]$$$。总和 $$$a_1 + a_2 + a_3 = 9$$$。