Obviously, you can sort the queries to solve the problem offline and use prefix sums to covert the question to "longest subarray with S[l] = S[r], L ≤ l ≤ r ≤ R.

Then, you can increase R and keep the answers for all L; it's just a matter of updating these answers when R is incremented. It can be done in .

First we use this Mo's algorithm to sort Query.

http://mirror.codeforces.com/blog/entry/7383

Let's call each group is a "bucket"

For each Query, we have to find i j which s[i] = s[j] and L<=i<=j<=R

Each i j has 3 cases :

1. i and j in bucket, so we can for, just O(sqrt(n))

2. i in bucket, j out of bucket. Let's call id1[s[j]]=j is the max position of s[j]. So answer is max(id1[s[i]]-i)

3. i and j out of bucket. Similar, call id2[s[j]]=j is the min position of s[j], so answer is max(id1[s[j]]-id2[s[j]])

I have solved it with MO's algorithm + segment tree for keeping track of the maximum value . Complexity is O( (N + M) * ROOT(N) * LOG (N) ) .

Here is the implementation http://ideone.com/YayNX7.

It would be good is someone can tell how to solve without the segment tree in O( (N + M) * ROOT(N) ).

Here is a editorial to a different problem with a similar solution.