Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### selfcompiler's blog

By selfcompiler, 5 years ago, ,

Hii I am trying to solve this problem http://www.spoj.com/problems/ZQUERY/ after thinking so many days i am not able to come up with efficient solution ,would any one like to suggest some idea, how to solve this ?

• 0

 » 5 years ago, # |   0 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 .
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 @Xellos Thanks , can you explain more how to solve efficiently to find the longest subarray with S[l]=S[r] ,L<=l<=r<=R,
•  » » 4 years ago, # ^ |   0 can you please explain the part keep answer for all L?
•  » » 4 years ago, # ^ | ← Rev. 2 →   -14 Xellos can you give your code ??
 » 5 years ago, # | ← Rev. 2 →   0 First we use this Mo's algorithm to sort Query.http://codeforces.com/blog/entry/7383Let'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<=REach i j has 3 cases : i and j in bucket, so we can for, just O(sqrt(n)) 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) 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]])
•  » » 5 years ago, # ^ |   0 pynhp9x can you explain bit more after query sorting step ?
•  » » » 5 years ago, # ^ |   0 Let's p = sqrt(n)Every query has L <= p is in bucket 1p < L <= 2*p is in bucket 2....With every query in the same bucket, sort query with increasing of R.
 » 5 years ago, # |   0 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) ).
•  » » 5 years ago, # ^ |   0 Could you please explain how did you solve it??
•  » » » 5 years ago, # ^ |   0 Have a look at codechef march challenge problem: qchef , it has a nice and detailed editorial.
•  » » » » 3 years ago, # ^ |   +1 Thanks Everyone now it is solved :)
 » 4 years ago, # |   +3 Here is a editorial to a different problem with a similar solution.