A16841 | $Replace and Sum$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

今天，KQ 在圣杯学院有一场考试。一位严格的老师布置了一道 KQ 无法解决的题目。他得到了两个长度为 $n$ 的数组 $a$ 和 $b$。KQ 被允许对数组执行以下操作： - 选择一个索引 $i$（$1 \le i < 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)$ 的最大值。

输入 #1

输出 #1

C++ 编辑器

输入

输出