Блог пользователя 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) только у чисел, которые существуют в множестве, то и остановиться мы можем только на таком числе.