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

Странная задача
Автор pva701, 13 лет назад, По-русски

Всем доброго времени суток, хотел попросить у вас совета или помощи. Решал вот такую задачу, задача что называется на реализацию. Получаю вердикт ва3... Не могу понять в чем проблема. Если что, вот мой код

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

13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Лично у меня есть только одна идея:
vector <int> level, vert, tr, ind, a;
for(int i = 3; i <= 2 * m; i++) a[i] = (x * a[i - 2] + y * a[i - 1] + z) % n;
изменить а на long long.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    нет, такую реализацию отправлял, тоже не помогает
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может ошибка в вашей реализации дерева отрезков? Я всегда делаю основание дерева равное степени двойки. И никогда не думал о том, обязательно ли это делать.
Порисовал картинки, что будет, если не степень двойки в основании. Похоже, что это и правда работает, но выглядит как шаманство :)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    да нет, в реализации думаю ошибки нет, если просто ЛСА надо найти, такая реализация работает, да и вообще я ее уже не раз писал, это действительно выглядит как шаманство, но работает
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Чтобы перестать думать, что это шаманство, нужно понять две вещи:

    1. Элемент с индексом 1 не является корнем дерева. Структура вообще не является деревом.
    2. Алгоритмы обходят структуру снизу вверх и никогда не делают наоборот.

    Неправильный взгляд:

              1
        2           3 
     4     5      6    7
    8 9  10 11  12 13

    Правильный взгляд (значения в 1 и 3 никогда не используются):

           2
        4     5      6
    7  8 9  10 11  12 13
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      > 2. Алгоритмы обходят структуру снизу вверх и никогда не делают наоборот.

      Ну это как раз спорно. Не ВСЕ алгоритмы так делают. Есть реализации дерева отрезков и сверху вниз. Лучше сказать, что при таком "хранении" дерева нельзя применять методы сверху вниз.
      Кстати, групповые операции (операции ко всем числам на отрезке) реализацией снизу вверх вроде не пишутся никак, поэтому мне совершенно не понятно, зачем не делать степень двойки в основании дерева. Разве что для уменьшения используемой памяти.

      Возможно, это и правильный взгляд. Но все равно не сильно очевидно, как это работает, так как указатели l и r  "магически" перемещаются с одного дерева на другое :)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        > при таком "хранении" дерева нельзя применять методы сверху вниз.

        Да, я хотел сказать именно это.

        Я писал здесь на CF статью об этой структуре. Чтобы не объяснять магические перемещения (они магические, даже когда размер отрезка степень двойки), я просто предлагаю думать, что это не дерево, а набор слоев отрезков.

        Также там описана реализация групповых модификаций с проталкиванием. Конечно, проталкивание можно сделать только сверху вниз. Но, во-первых, это нужно только для проталкивания (все остальное, в том числе сама модификация, происходит снизу вверх). Во-вторых, в этой структуре нельзя просто встать в корень и пойти проталкивать — нужно сначала подняться снизу, а потом повторить последовательность в обратном порядке.
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Почему это групповые операции при реализации снизу вверх никак не пишутся? Отлично пишутся и так и так. (правда возможно я не до конца понимаю, что для вас есть снизу вверх, а что есть сверху внизу (для меня снизу вверх - когда от одного элемента поднимаешься к сумме/max/min/ещё-что от нескольких)).
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          не расскажете, как это можно реализовать, или может датите ссылку? а то я до этого момента тоже полагал, что обновлять на отрезке снизу невозможно и когда искал как это сделать, так ничего и не нашел...

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

            http://sites.google.com/site/kennyhorror/c/intervaltree

            Вот реализация того, что я понимаю под данным видом дерева с нахождением суммы и прочего снизу (правда, после переделки на класс и шаблон оно стало менее шустрым и понятным).

            PS: Элемент 0 в дереве использовать нельзя иначе есть мелкая бага.

            → Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Попробуй такой тест:
10 100
0 0 8 6 7 2 4 1 0
9 8
49 82 95
Правильный ответ на него : 180
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    спасибо, действительно на этом тесте почему то не работало( ну сейчас все исправил, все прошло) всем спасибо
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Откуда тест? Получен стресс-тестом? На самом мне теперь интересно, где же в решени баг? :)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это как раз тест #3, на котором решение падало в проверяющей системе. 
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
раз уж создал тему, спрошу тут, кто нить может подкинуть задачи сводимые к ЛСА?
→ Ответить