Блог пользователя besher

what is the best algorithm for this problem?
Автор besher, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Link

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

At each node we will save answer for current segment.

UPD: Wrong

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить