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

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

Всем доброго времени суток. Наткнулся на задачу, даётся n,m массив A длинны n(n<=100000), далее нам требуется отвечать на m(m<=100000) запросов вида l,r,x требуется на отрезке от l до r найти первое A[i]>=x(и вывести i). Если кто знает как решать прошу в комментарии описать свою идею.

UPD Огромное спасибо I_love_Tanya_Romanova и linjek за исчерпывающие ответы. Ну и конечно Neodym за шутку.

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

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

Прочтите о дереве Фенвика.

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

    Извини за возможно глупый вопрос, но что это мне даст?

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

      Предположу, что ALEXKIRNAS хотел сказать что-то такое:

      Сожмем входные числа, отсортируем запросы по спаданию левого края, будем обрабатывать массив справа налево, в каком-то массиве Х будем для каждого числа из входных данных хранить самое левое из его вхождений, которое мы уже встретили (или INF, если такого числа еще не было), и после добавления числа на позиции t считать ответы на все запросы, в которых l=t. Тогда ответ на запрос l r x — это минимум из значений Х[i] по всем i>=x, или -1/No solution, если этот минимум больше r. Для нахождения минимума на суффиксе массива можно использовать дерево Фенвика.

      Но здесь слишком много букв, он написал немного короче:)

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

    Лучше Бинарным поиском.

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

      Эмм... не получится бинарным поиском. Бинарный поиск применим только к монотонным функциям. А в условии не сказано что массив отсортирован. Тут скорее дерево отрезков.

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

        Как раз таки можно. На каждый запрос делаем бинарный поиск от l до r. Пускай у на есть middle. Проверяем, что максимум на отрезке [l, middle] >= x. для нахождения максимума на отрезке можно использовать sparse table.

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

          Что-то я не понял. Проверили, и что? Если максимум больше x, то надо идти вглубь этого отрезка, так? А если и max([middle+1, r])>x, то мы и вправо должны пойти. И где тут будет меньше O(n)? Например массив состоит только из чисел 2, а во всех запросах x=1.

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

            Внутри бинарного поиска проверяем, есть ли на отрезке число, которое не меньше х (это делаем за О(1) с помощью sparse table). Нам нужно с помощью бинарного поиска найти наименьшую длину, для которой это выполняется — понятно, что на отрезке этой длины искомым является последний элемент, потому что на более коротком отрезке без одного последнего элемента наше условие уже не выполняется.

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

Ну можно написать за O(m*log(n)*log(n)) — с помощью бинпоиска от l до r и дерева отрезков.

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

    Если возможно опишите поподробнее решение.

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

      Будем считать что числа содержатся от 1 до n в массиве. Строим дерево отрезков на изначальном массиве. (В вершине будем хранить номер вершины j, a[j] — которое максимальное, если у обоих сыновей значения равны, то берем минимум.), пусть это функция f, зависящая от 5 параметров. int f ( int v, int tl, int tr, int l, int r) Переходим к запросам , для каждого из них: r1=r; l1=l; While (r1-l1>0) { int mid = (l1+r1)/2; if ( a[f(1, 1, n, l, mid)]>=x) r1=mid; else l1=mid+1; } в f(1, 1, 1, n, l, l1) искомый ответ. Сорри что все слитно, до сих пор не понимаю как тут перенос делать.

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

        Раз уж подняли тему.

        Перенос делается двумя переводами строки.

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

      Или кстати можно те же sparce table написать, предподсчет тогда за nlogn , и потом тем же бин поиском находить ответ, тогда получится в итоге. ( (n+m)logn).

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

    А потом избавиться от одного логарифма, находя ответ сразу при спуске по дереву. А потом обойтись деревом фенвика, заметив, что r в запросе ни к чему.

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

Прочитал название блога как "Не отказался бы от Польши". Не знал уже, что и советовать.

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

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

      Ненавижу CF. Всякие смищные баяны почему-то собирают плюсы

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

        К сожалению, таков уровень интеллектуального развития большинства местных пользователей.

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

          Мне, кстати, не очень нравится негласное правило "видишь любую дискуссию — плюсуй того, у кого больше рейтинг", но вас минусуют даже за адекватные комменты. Традиция наверно:)

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

            Я зашёл в эту ветвь когда был только комментарий "Ненавижу CF. Всякие смищные баяны почему-то собирают плюсы" и я поставил ему решительный минус, ибо это комментарий под своим же сообщением. Непонятно зачем человек воскресил пост месячной давности, возможно кармодрочерства ради. И да, поскольку у этого комментария +10, то как минимум 11 "интеллектуалов" здесь присутсвуют.

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

            Не надо иметь образование психолога, чтобы понять — если кто-то называет других тупыми идиотами, то у части из них может сформироваться субъективное негативное отношение к данному человеку и всем его высказываниям:)

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

Можно ссылку на задачу? Не понимаю почему нельзя решать проходом по массиву слева направо, поддерживая set из активных запросов, упорядоченный по x, тогда будет m*lg(m)(отсортировать запросы и расставить метки) + n (пройтись) + m*lg(m) (обработать). Хочу проверить.