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

221D — Little Elephant and Array
Автор Tribbiani, история, 11 лет назад, По-английски

I've solved this problem using sqrt decomposition. but how can i solve it using segment tree?

Thanks in advance :)

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

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

You can solve this problem without sqrt decomposition and segment tree. See this 11088217 submission

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

That solution uses the idea that since we're asking for all numbers x that have at least x occurences, and the maximum number of elements is 105, the maximum amount of such numbers is 446, because .

While it's not Mo's algorithm or dividing the queries into buckets, it's still based on the concept of square root.

→ Ответить