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

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

Дан массив A. И даны K запросов. Каждый запрос имеет вид: 1. 1 L R D: прибавить число D К отрезку L R 2. 2 L R X: Узнать количество чисел равных X на отрезке L R.Помогите решить

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

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

Откуда задача?

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

Ограничения хоть какие-то скажите. МБ там проходит тупой алгоритм))

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

    N,K<=10^6

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

      UPD: ошибся

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        1. 1 L R D: прибавить число D К отрезку L R

        У вас этот запрос тоже за log^2 работает? Если это так, то можно подробнее, как это написать?

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

          Тяжело. Я ошибся. Почему-то показалось, что с отложенными операциями всё будет хорошо.

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

            В принципе можно:

            http://mirror.codeforces.com/blog/entry/15527#comment-204656

            Но пока дальше идей дело не сдвинулось.

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

              Боюсь, что тогда всё что можно сделать — то же самое, но теперь хранить декартовы и мёржить их каждый раз, обновив всё поддерево (увеличив в нём отрезок и пересортировав его). С ходу не скажу, насколько плохой становится асимптотика.

              UPD: ясно, в чём пробема. Мы не можем мёржить, т.к. ключи левого поддерева не всегда меньше всех ключей правого. Будем вынуждены мёржить добавляя элементы по одному.

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

                Да уж, задачка =). Похоже за log^2 не решить.

                Не знаю, бред или нет: а что если как-то предподсчитать вначале, сколько раз каждая нода будет использоваться в запросах, и потом как-то хитро решать, стоит ли вызывать мердж, или просто лишний раз спуститься ниже. То есть как-то высчитывать, что быстрее можно будет выполнить (по сути еще решать задачу об оптимальном мердже =) )

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

Я уже спрашивал, как решать такую задачу.

→ Ответить