How to solve this range based problem!!

general
,
1

Given an array of length N Every element of the array will be less than or equal to a given value M.At every level you will be given two integers L and R. your task is to output the answer of the following pseudocode at each level.

ans=0

for i=L to R

for j=L to R

    if(a[i]==a[j])

        ans=max(ans,j-i)

print ans

Input Format

First line contains 3 integer N,M,Q.

N=Total number of elements in the array.

M is the maximum limit of Ai.

Q is the number of queries to be processed.

Constraints

1<=N,Q,M<=10^5

1<=Ai<=M

1<=L<=R<=N

Output Format

For each query print the required answer in new line.

Sample Input

5 3 3

1 2 3 2 1

1 4

2 5

1 5

Sample Output

2

2

4

Explanation

  1. a[2]=2, a[4]=2 ans=4-2=2

  2. a[2]=2, a[4]=2 ans= 4-2=2

  3. a[1]=1 , a[5]=1 ans=5-1=4

Can someone tell me an efficient approach??

can it be solved with Mo Algorithm?

2 Likes
2

First of all, if I’ve understand the problem correctly, the search could be incremental:
found out the pair (i, j) [with j > i], as soon as i would become j, obviously the right pair is (j, i).

Secondly, the idea could be to use functions/methods by libraries:
using C++, I’d use the rfind method in string class in order to find the last index in which there is the given letter.

In code:

string a = "aBBBBBBa";
int i = 0, j = a.rfind(a[i]);

and then I’ve the pair (i, j) looked up.

Maybe you just use Java, there is a useful method called ‘LastIndexOf’ for class String.

Hope this will help you.
Best Wishes

3

Nice approach but I don’t think this will fit inside time limit. As you will have to use rfind for all a[i] in (i,j) and this will surely exceed time limit I suppose!

4

Try to think of mo’s with map/segment tree.

1 Like
5

@vivek_1998299 can you elaborate a bit more?
And @raman3217 can you please provide the link to the question… I am interested in trying it out!

6

@vivek_1998299 I thought of mo’s but not getting how to apply it with map/segment tree!!
can you explain a little bit more?

7

Exactly this approach will get TLE!!

8

Ohk ,i’ll tell u the approach with mo and segment.

This question is equivalent to finding the max difference of index of two same elements in a range.

So lets say i have an element x,and lets say indices 3,5,8 lies in [L,R] ,so max ans due to this x can be (8-3)=5

Now we need to calcuale this for all x ,and take max of all

Lets have a max segment tree.

So lets consider the insert operation for mo.
Define a map array of M elements map[M] to store the indices ,where map[x] will contain all the indices (inserted by insert operation/during mo)

So coming back to insert,
Lets say i got an element x,and i am at index j,so do the following map[x].insert(j)
So now ansDueToX=map[x].max-map[x].min
and now in segment tree do point update for x with value ansDueToX

Similarly for delete oprn in mo,

Lets say i got x,and i am at index j,then map[x].erase(j),ansDueToX=map[x].max-map[x].min,and update this at point x in segment.

Now after insert ,delete done ,just query segment for max in range [0,M] which is ans for a query

3 Likes
9

thank you so much got it!!!

10

Cool approach… Thank you for sharing :slight_smile:

11

Thanks for the link!

12

GOT AC !!
Learnt something new , thanks man @vivek_1998299 awesome approach !!
not have enough reputation otherwise upvoted your answer!!!

13

We can also keep the max values for elements in the current range in a multiset instead of a segment tree.

14

@raman3217 can you please share your code… I am trying to code on my own but if I get WA,maybe it would be a good reference.

15

@raman3217 I didnt expect it to pass ,as the constraints were strict,and yeah u could try @meooow’s way out also(should be faster).

1 Like
16

My code fails on Test Case 2 :frowning:
I tried to find the bug and even compared my code with @raman3217’s. It would be great if anyone could spot the bug!
Here’s the link to my code: https://ideone.com/9R37OL
Thanks in advance :slight_smile:

17

U cant change the sequence of moving left and right pointer in mo’s.

Ur ac code: https://ide.geeksforgeeks.org/gi8XKDfixD

1 Like
18

Ohh yeah… Stupid me xD
Thanks for the help :slight_smile: