white_coder's blog

segment tree problem.
By white_coder, 13 years ago, In English

Can anyone please give me hints,how to solve this problem.

1083 — Histogram PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 64 MB

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3 measured in units where the width of the rectangles is 1.

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram. Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case contains a line with an integer N (1 ≤ N ≤ 30000) denoting the number of rectangles. The next line contains N space separated positive integers (≤ 30000) denoting the heights. Output

For each case, print the case number and the largest rectangle that can be made. Sample Input

Output for Sample Input

2

7

2 1 4 5 1 3 3

5

4 4 3 2 4

Case 1: 8

Case 2: 10 Note

Dataset is huge; use faster I/O methods.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
13 years ago, hide # |
← Rev. 3  
Vote: I like it +3 Vote: I do not like it

This problem has a O(n) solution with stack but It seems like you are interesting on Segment Tree.

You have an array of rectangle example [4 4 3 2 4], you can get a area of length(5) * minimum in the array(2) that it is 10. In order of use a bigger height you have to delete the 2 so split the array [4 4 3], [4] and make the same problem recursive. 

getArea(N){
   int i = position_of_min(N);
   A = N[0:i-1];
   B = N[i+1,len(N)];
   return max(N[i]*len(N), max(getArea(A), getArea(B)));
}

You can use segment tree to do position_of_min(N) in O(log(n)) or You can use sparse table to do position_of_min(N) in O(1), and the solution will be O(n*log(n)) or O(n).

→ Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks for your reply,can you tell me the O(n) solution with stack.

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      My implementation is here.

      The gist:

      • Scan from left to right.
      • Add to the stack when height is going up.
      • Otherwise, this marks the end of a (previous) taller rectangle, which is checked for area.
      → Reply