К-ая порядковая статистика

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

Автор fiter, 10 лет назад, По-русски

Как искать К-ую порядковую статистику на отрезке используя НЕ ПЕРСИСТЕНТНОЕ дерево отрезков. И вообще, возможно ли это?

UPD: ссылка на задачу — http://www.e-olimp.com.ua/ua/problems/3866

структуры данных

fiter
10 лет назад
11

Комментарии (11)

Написать комментарий?

MrDindows

10 лет назад, # |

Возможно.

Бинпоиск по ответу. В функции-проверке будем подсчитывать количество чисел меньше проверяемого. Для этого в каждой вершине ДО будем хранить отсортированный кусок массива и запускать бинпоиск по нужным кускам. Итого $\text{[math]}$ на запрос. Как раз под ограничения задачи.

→ Ответить

proVIDec

10 лет назад, # ^ |

← Rev. 2 →

+13

Если еще в вершине для каждого элемента в отсортированном списке хранить индекс большего по величине в левом и правом сыновьях, то второй бинпоиск не нужен (индекс можно пересчитывать в спуске), получается $\text{[math]}$ на запрос :)

→ Ответить

fiter

10 лет назад, # ^ |

← Rev. 4 →

MrDindows, получается нужно чтобы в бин. поиске(который по ответу) рассматривались только числа которые есть на текущем отрезке. Как это сделать?

→ Ответить

adamant

10 лет назад, # ^ |

Явно хранить их в отсортированном виде в вершине.

→ Ответить

fiter

10 лет назад, # ^ |

Та это понятно. Только вот такой тест: 5 2 6 3

Найти на отрезке 1..4 3 элемент.

Если искать это бин. поиском то может оказаться что ответ 4, но 4 на отрезке нет. Надеюсь понятно написал о чем думаю.

→ Ответить

adamant

10 лет назад, # ^ |

-8

Ну можно попутно в каждом подотрезке найти lower_bound найденного значения и выдать ответом минимум из этих чисел.

→ Ответить

MrDindows

10 лет назад, # ^ |

← Rev. 4 →

Если считать количество чисел не строго меньше, а меньше либо равно, то будет классический бинпоиск.

while(l<r)
{
  int m = (l + r)/2;
  if (foo(m) >= k) r = m;
  else l = m + 1;
}
ans = l;

// Функция foo(m) считает количество чисел меньше либо равных m

→ Ответить

fiter

10 лет назад, # ^ |

← Rev. 2 →

-14

MrDindows, имелось ввиду что бин. поиск может найти такое число которого нет на отрезке!

→ Ответить

adamant

10 лет назад, # ^ |

Можно заметить, что тот вариант бин. поиска, который он описал найдёт как раз то, что нужно, если внимательно его изучить.

→ Ответить

fiter

10 лет назад, # ^ |

adamant, я не понимаю, почему именно этот бин. поиск должен работать(не находить число, которого нет на отрезке). Можете обьяснить?

→ Ответить

adamant

10 лет назад, # ^ |

Этот бин. поиск находит первое число, для которого количестве элементов, меньше либо равных ему равно k. Так как foo(x)>foo(x-1) только у чисел, которые существуют в множестве, то и остановиться мы можем только на таком числе.

→ Ответить