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, In English,

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 ?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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 :

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    pynhp9x can you explain bit more after query sorting step ?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain how did you solve it??

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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