besher's blog

what is the best algorithm for this problem?
By besher, 9 years ago, In English

Given n numbers and m queries for each query (L R) find the most frequent number from L to R and how many times it occurs in this interval

for example:

input:

7 3

3 5 3 5 5 3 3

2 4

3 3

1 3

output:

5 2

3 1

3 2

thanks in advance.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Link

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! Please write the link of problem statement. I couldn't find that. Thanks

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think it can be solved by Treap or segment tree.

At each node we will save answer for current segment.

UPD: Wrong

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Imagine we know answers for [l, mid) and [mid, r).
    How to combine these answers and find it for [l, r)?

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use MO's algorithm to solve, you can find detailed explanation here : http://blog.anudeep2011.com/mos-algorithm/

→ Reply