bro can anyone just explain me the logic to solve this problem. i just want to know the approach using binary search not segment tree @karangreat @ssjgz @ssrivastava990
Problem link ? (20 characters)
What a great problem! Completely blown my mind! I’ll take some time to explain the solution
The problem is really good.
Yup, I took full 15 minutes of isolation to reach the solution , that too I guess I had luck : p
He is a pro.
I am writing the solution !
yo bro… lets when we will reach there.
ok bro (20 characters)
Short solution:- for each ‘i’, you do binary search and find what will be the longest subarray starting from ‘i’ which will satisfy the condition.
For any (l,r), quickly, do a binary search and find a guy which just touches ‘r’.
All guys which did not touch will be added normally, all other in simple other way.
Long Solution:-Morning ko!
isko help karo koi?
Use two pointers in precomputation.
For each l, find max r which can be taken so that it follows this condition and just store all such r in an array ( a[l]=r )
Now also keep prefix sum of this array.
Values of r will always be increasing.
So now given l,r , binary search on r ( find value smaller than or equal to r ( do not do this on prefix sum array) ).
Now let this index be k.
So answer = pre[k] - pre[l-1] - ( k-l+1) ( roughly)
And also answer += r*(r-k) -(r-k) ( roughly again)
So idea is to find max r for each l ( let max r for each l1 be r1 and so on).
Then
Subarrrays (l1,l1) , (l1,l1+1) , (l1,l1+2),…( l1,r1) will be valid. So we fix l and find all possible r for it.
So this is my approach.
@l_returns bro i have understood some part can you explain with an example on-0001100
(l,r)=(2,7) and k=2
and how did you wrote that formula