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