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 ?

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3496 |

3 | apiadu | 3438 |

4 | TLE | 3356 |

5 | LHiC | 3339 |

6 | mnbvmar | 3281 |

7 | 300iq | 3267 |

8 | Radewoosh | 3242 |

9 | yosupo | 3233 |

10 | 1919810 | 3203 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 168 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

7 | Um_nik | 161 |

9 | rng_58 | 156 |

10 | Petr | 154 |

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 ?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2020 12:38:37 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Rand keep the answers for allL; it's just a matter of updating these answers whenRis incremented. It can be done in .@Xellos

Thanks, can you explain more how to solve efficiently to find the longest subarray with S[l]=S[r] ,L<=l<=r<=R,can you please explain the part keep answer for all L?

Xellos can you give your code ??

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

http://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 :

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]])

pynhp9x can you explain bit more after query sorting step ?

Let's p = sqrt(n)

Every query has L <= p is in bucket 1

p < L <= 2*p is in bucket 2....

With every query in the same bucket, sort query with increasing of R.

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) ).

Could you please explain how did you solve it??

Have a look at codechef march challenge problem: qchef , it has a nice and detailed editorial.

Thanks Everyone now it is solved :)

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