Largest Rectangle in a Histogram and Queries
Time limit4sMemory limit512 MB
Given a histogram of N bars, each query asks for the height of the width-w rectangle inside bars l to r that has the largest area.
- Level
Hard8 of 10
- Topics
- Segment tree, Sliding window, Array
- Solved
- No attempts yet
Problem
A histogram is a shape made of several rectangles lined up along the bottom. Every rectangle has the same width of 1, but their heights can differ. For example, the figure on the left is a histogram with rectangles of heights 2, 1, 4, 5, 1, 3, 3.
Perform the following Q queries on the histogram.
l r w: Consider only the rectangles from the l-th to the r-th. Print the height of the rectangle with width w that has the largest area.
Input
The first line contains the number of rectangles N. The second line contains N integers h1, ..., hN. These are the heights of the rectangles in the histogram, given in order from left to right. The width of every rectangle is 1.
The third line contains the number of queries Q. The next Q lines, starting from the fourth line, contain the queries.
Constraints
- 1 ≤ N, Q ≤ 100,000
- 1 ≤ hi ≤ 1,000,000,000
- 1 ≤ l ≤ r ≤ N
- 1 ≤ w ≤ r-l+1