aya1909's blog

Help needed to solve this problem!!
By aya1909, history, 4 years ago, In English

You Are given an array A of N integers. You have to answer Q queries of form L R. Answer to each query is sum of lengths of all sub arrays in A whose maximum element lies in range [L,R].

Constraints:

1<=N,Q<=3*10^5 1<=A[i]<=10^9 1<=L<=R<=10^9

Input: 5 3 1 2 3 4 5 1 3 1 5 5 5

Output:

10 35 15

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aya1909 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

For each position calculate the nearest greater element both on the left and on the right.

For example, array [1, 5, 2, 6, 3, 3, 2, 1, 5, 4]. For 6-th element it will be 4-th element (nearest non-lower on the left) and 9-th (nearest greater on the right).

For array [2,2,2,2] for 3-rd element assume L=2 and R=4 (L<i<R).

Now form such segments: for each element i the segment will be (L, R). For example, for 6-th element the segment will be (4,9) = {5,6,7,8}

Now you can operate with such segments. For example, you need to calcuate number of segments that have maximum in range [L;R]. If you look carefully through each element, you can see the following:

In our segment we have L, i and R (i is the position of the initial element, in our example L=4, i=6, R=9). So, there are (i-L+1)*(R-i+1) segments have maximal element a[i]. You can also calculate the sum of lengths (it is also not hard).

Now you can answer each query in O(1).

P.S. Please don't downvote me if this solution is wrong, that can happen sometimes.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    L and R are values actually not range. 1st query is 1 3 which means sum of all length of subarrays which have {1,2,3} as maximum elements.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Yes, I know. With this approach you can get the sum of lengths of all segments with maximal element not bigger than R (because you have n groups of segments).

      If this value is f(R), than you need to calculate f(R)-f(L-1) to get the answer.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        For each element of array, we can calculate sum of lengths in this way. Sort the array and calculate prefix sum of calculated lengths for each element in pre array and pre[idx2]-pre[idx1] will be answer, where idx2=upper_bound(R)-1; and idx1=lower_bound(L)-1;

        Right??

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Firstly scale the input (not only values in $$$A[i]$$$ but also bounds from queries). Create segment tree $$$T$$$ which will store the answer. An answer to query $$$[A; B]$$$ will be the sum on segment $$$[A; B]$$$ in $$$T$$$. Then run the following recursion: let's say we are in range $$$[L; R]$$$ and maximum value of $$$A[i]$$$ where $$$L \leq i \leq R$$$ is located in index $$$j$$$ and is equal to $$$M$$$. If there are several maximums on this segment choose leftmost. Now count the sum of lengths of segments which go through index $$$j$$$ and doesn't go beyond $$$L$$$ and $$$R$$$ (to be precise: sum of lengths of such segments $$$[A; B]$$$ that $$$L \leq A \leq B \leq R$$$ and $$$A \leq j \leq B$$$). Let this sum be $$$S$$$. Now you only need to update the segtree $$$T$$$ which store the answer. Simply add $$$S$$$ in point $$$M$$$ and continue recursion on segments $$$[L; j - 1]$$$ and $$$[j + 1; R]$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Don't post your solutions to this problem. It's is From an Ongoing Hiring Contest which will end on October 18. Delete the blog ASAP !!!

→ Reply