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

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

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
  • Проголосовать: не нравится

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

Link

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

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

→ Ответить
»
12 лет назад, скрыть # |
← 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

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

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

→ Ответить