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

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

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

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

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

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

Возможно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// Функция foo(m) считает количество чисел меньше либо равных m
          → Ответить
          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

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

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

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

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

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

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

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

                  → Ответить