4993:最大矩形和-1

时间限制:2 S   /  内存限制:65536 KB
AC:24   /  Submit:40
问题描述

给你一个长度为 $$n$$ 的一维矩阵,有 $$q$$ 次查询,每次查询给定一个下标 $$x$$ ,求以 $$x$$ 为左边界,你能找到的最大矩形和。

例如给你一个长度为 $$5$$ 的一维矩阵: $$\begin{bmatrix}0,1,-1,1,1\end{bmatrix}$$ ,如果以下标 $$2$$ 作为左边界,那么能够构成最大矩形和的右边界是 $$5$$,和为 $$2$$ 。(不会不包含元素)

输入描述

 第一行先是一个正整数 $$n$$ 表示一维矩阵的长度。$$(n\le 1e5)$$

接下去一行,包含 $$n$$ 个元素 $$a_i$$。$$(-1e5 \le a_i \le 1e5)$$

接着是一个正整数 $$q$$ 表示查询次数 $$(q \le 1e5)$$

然后 $$q$$ 行,每行一个值 $$x$$ ,表示询问你以下标 $$x$$ 作为左边界,能获取的最大矩形和是多少。$$(1 \le x \le n)$$

输出描述

针对每次查询,输出以 $$x$$ 为左边界的最大矩形和。

样例输入复制样例

5

0 1 -1 1 1

2

2

3

样例输出

2

1

相关

题单#5(前缀和、差分数组)


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1