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

Timus 1028
Автор Krot, 14 лет назад, По-русски
Че-то никак мысли не приходят, вроде простая задача должна быть, на форуме написано, что решается множеством способов. Может кто-нибудь подробно написать решение? 
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Множеством? Тоже интресно тогда, ибо знаю только через дерево фенвика, ну или  RMQ.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У нас на кружке это любимая задача, когда приходит время открыть страшную тайну о структурах данных - они бывают полезны.

    И она используется при изучении следующих тем:

    - sqrt-декомпозиция

    - дерево Фенвика

    - дерево отрезков

    - декартово дерево
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А как её через RMQ решить?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если RMQ по-вашему это дерево отрезков, то вроде там надо немного извратиться, чтобы прошло по памяти?
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Извиняюсь, там опечатка, имелось ввиду RSQ. Да и к тому же, я это писал полгода назад, тогда любое дерево отрезков так и называл :)
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Другими словами задача следующая: для каждой точки нужно посчитать количество точек, которые не выше и не правее данной.
Отсортируем все точки по координате X, при равенстве X - по Y. Очевидно что в получившейся последовательности для некоторой позиции i, все точки имеющие позиции большие чем i находятся либо правее либо выше (с учетом того, что двух одинаковых точек быть не может). Причем все точки которые имеют позиции меньшие чем i находятся не правее. Т.е задача свелась к тому, что нужно для каждой точки определять сколько точек из тех, что находятся в отсортированной последовательности левее данной, находятся не выше.
Для этого сделаем следующее:
Заведем нитервальное дерево для суммы, изначально пустое. Будем идти по отсортированным точкам. Level текущей точки будет сумма в дереве от 0 до Y текущей точки. После того, как мы узнали Level текущей точки, нужно увеличить элемент с номером Y текущей точки на единицу.
Вот так будет работаеть тест из примера:


изначально есть:
(1 1), (5 1), (7 1), (3 3), (5 5)
после сортирования:
(1 1), (3 3), (5 1), (5 5), (7 1)

Собираем решение:

итерация 1.
дерево сумм[0.. maxY]: 0 0 0 0 0 0
ответ [0.. n - 1]: 0 0 0 0 0
позиция 0:
Берем в дереве сумму с 0 по 1, она равна 0. в ответ добавляем одну точку 0 уровня. В дереве увеличиваем элемент [1] на единицу.

итерация 2.
дерево сумм[0.. maxY]: 0 1 0 0 0 0
ответ [0.. n - 1]: 1 0 0 0 0
позиция 1:
Берем в дереве сумму с 0 по 3, она равна 1. в ответ добавляем одну точку 1 уровня. В дереве увеличиваем элемент [3] на единицу.

итерация 3.
дерево сумм[0.. maxY]: 0 1 0 1 0 0
ответ [0.. n - 1]: 1 1 0 0 0
позиция 2:
Берем в дереве сумму с 0 по 1, она равна 1. в ответ добавляем одну точку 1 уровня. В дереве увеличиваем элемент [1] на единицу.

итерация 4.
дерево сумм[0.. maxY]: 0 2 0 1 0 0
ответ [0.. n - 1]: 1 2 0 0 0
позиция 3:
Берем в дереве сумму с 0 по 5, она равна 3. в ответ добавляем одну точку 3 уровня. В дереве увеличиваем элемент [5] на единицу.

итерация 5.
дерево сумм[0.. maxY]: 0 2 0 1 0 1
ответ [0.. n - 1]: 1 2 0 1 0
позиция 4:
Берем в дереве сумму с 0 по 1, она равна 2. в ответ добавляем одну точку 2 уровня. В дереве увеличиваем элемент [1] на единицу.

дерево сумм[0.. maxY]: 0 3 0 1 0 1
конечный ответ [0.. n - 1]: 1 2 1 1 0

Вот так мы получили ответ. Для того, чтобы посмотреть как строить дерево для сумм, можно почитать на вики статю про RSQ, или дерево Фенвика. Запросы взять сумму и обновить элемент дерева будут работать за log(maxY), всего такиз запросов нужно будет выполнить N. Итого вычислительная сложность порядка Nlog(N)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
При данных ограничениях проходила также sqrt-декомпозиция.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Не туда :(

    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А как через sqrt решать? Я придумал : сортируем, разбиваем на sqrt(n) блоков в каждом блоке храним отсортированный вектор игреков. Потом для запроса бежим по блокам и в каждом блоке за lon(maxy) lower_bound ищем кол-во.
    сложность o(n*sqrt(n)*log(maxy))
    Может можно как-нибуть по-другому?
    Напишите пожалуйста!
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, я по-другому решал. Координаты x и y целые и не превышают 32000. Разобьем квадрат [0;32000]*[0;32000] на примерно 32000 карманов (скажем, на квадраты со стороной 179). Далее считываем ввод и сохраняем, в какой карман попало сколько точек. Очевидно, если карман i находится выше и правее, чем карман j, то и все точки из кармана i находятся выше и правее, чем все точки из кармана j.
      ...Дальше, если честно, я не очень помню (давно это было:)), но если надо, могу скинуть код, который дает АС за 0,062 секунды..)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        всё гораздо проще, если отвечать на входные данные сразу. ( онлайн )

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

        в итоге задача свелась к нахождению количества чисел находящихся не правее данного. 

        и теперь можно делать sqrt-декомпозицию только для [0;32000], а не [0;32000]*[0;32000]. =)

        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          ...Да, наверное, я все-таки так делал:))
          А то не могу толком разобраться в своем коде годичной давности:)
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Когда-то давно решал эту задачу. Ради интереса глянул исходник. Оказывается прошел тупой insert в вектор и upper_bound. Тогда я не знал Фенвика, Дерева отрезков. Сейчас бы ни за что не написал такое решение :)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вспомнил тот прикол, что когда я стал соадмином одного АСМ-сайта, и начал иногда из интереса читать коды знакомых по некоторым задачам, то сразу нашел штук 10 задач, где кривые тесты и проходит явный бред:)

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

    А эту задачу с тимуса я тоже sqrt-декомпозицией делал.

    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
маленькое замечание - делайте ссылку на задачу!..
→ Ответить