Hello all,
This is my first blog entry on Codeforces. So please forgive me if I am not following any regulation. I recently came across a question.Its statement goes like this:
Given an array A1,A2...AN. We are asked to count the number of contiguous subarrays Ai,Ai+1...Aj such that 1≤i≤j≤N and the largest element of that subarray occurs only once in that subarray.
For example: If N=3 A[3]={1 2 3} => Ans=6 || If N=4 A[4]={2 2 1 2} => Ans=6
Constraint: 1<=N<=10^5 and 1<=A[i]<=10^5
I have the Naive approach which works in O(n^2) but as evident from constraints it would give TLE. So please help to optimize the solution. Thanks.
Auto comment: topic has been updated by Nams (previous revision, new revision, compare).
Let's fix some element which will be the maximum and will occur only once. This can be done with a for-loop over the elements. Say the current index is i. We need to find two integers — L (the length of the maximum contiguous subarray ending at index i-1 containing only elements which are less than A[i]) and R (the length of the maximum contiguous subarray starting from index i+1 containing only elements which are less than A[i]). Then obviously (L+1)*(R+1) should be added to the answer. Now we need to find those L and R fast. This is actually very similar to finding the largest rectangle in histogram so we can now solve the problem in O(N).
Thanks P_Nyagolov. I got it.
There was an issue with my first idea. This is the correct one:
For each
i, calculate the amount of values smaller thanv[i]before and afteriand call itl[i]andr[i]. Addl[i]*r[i]to the answer. The naive implementation would be O(N2), but if you keep a segment tree and update it after each element is processed you get O(NlogA).My accepted solution: http://ideone.com/gtfjYU
Nams where can I submit the problem?
Hi Branimir. You can try it here:Sherlock and Subarrays
Thanks