### aya1909's blog

By aya1909, history, 5 months ago,

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

• -4

 » 5 months ago, # |   0 Auto comment: topic has been updated by aya1909 (previous revision, new revision, compare).
 » 5 months ago, # | ← Rev. 2 →   +1 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
•  » » 5 months ago, # ^ |   +8 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » 5 months ago, # ^ |   +8 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??
•  » » » » » 5 months ago, # ^ |   +3 Something like this, yes.
 » 5 months ago, # | ← Rev. 2 →   +8 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]$.
 » 5 months ago, # |   +13 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 !!!