Subarray Sum Queries II

题目描述

给定一个长度为 n 的整数数组和 q 个查询。对于每个查询，你的任务是计算区间 [a,b] 内的最大子数组和。 允许空子数组（和为 0）。

输入格式

第一行包含两个整数 n 和 q：元素个数和查询个数。 接下来有 n 个整数 x_1,$\ldots$,x_n：数组的内容。 最后有 q 行描述查询。每行包含两个整数 a 和 b。

输出格式

对每个查询输出答案。

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

6
7
0
3

提示

$1 \le n, q\le 2 \cdot 10^5$ $-10^9 \le x_i \le 10^9$ $1 \le a \le b \le n$

标签: CSES3226|区间查询

来源

CSES3226|区间查询