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

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

Дается задача:
Дается N карт, на обеих сторонах каждой карты написано одно число. Если вы положите карту на стол одной стороной вверх, то вы не сможете увидеть число, написанное на другой стороне.
Есть N карт на столе, пусть Ai — число, написанное на одной стороне карты i, a Bi — число, написанное на другой стороне карты i. Карты лежат вначале в таком положении, что видно число Ai.
Дается К операции, для каждого j от 1 до К выполняется следующая операция: перевернуть все карты, числа на которых меньше равны Tj.
Результатом является сумма чисел, которые видны на картах после этих К операции.

1<=N,K<=200 000
1<=Ai,Bi,Tj<=1 000 000 000

Sample test:

    Input:     
 5 3 // N и K      
 4 6 // N строк каждая содержит цифры на сторонах карт Ai и Bi      
 9 1       
 8 8      
 4 2       
 3 7      
 8   // K строк, каждая содержит Tj        
 2          
 9     
    Output:
 18     
  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

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

Несколько подсказок:

  • Структуру данных нужно строить над операциями, а потом для каждой карты по отдельности найти ее конечное положение;
  • Для карты (a, b) все запросы можно разделить на 3 типа:
    1. Tj < min(a, b) — ничего не меняет;
    2. min(a, b) ≤ Tj < max(a, b) — переворачивает карту числом max(a, b) вверх;
    3. Tj ≥ max(a, b) — переворачивает карту вне зависимости от положения.
»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Найдем для каждой карты ее состояние после всех запросов.
Пусть, для определенности, Ai < Bi (в противном случае все аналогично). Тогда найдем последний запрос, для которого Ai <  = Tj < Bi. После выполнения такого запроса карта будет лежать стороной Bi. Дальше останется посчитать, сколько после найденного запроса есть запросов с T ≥ Bi — столько раз нужно перевернуть карту после этого.

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

    А как найти такую последнюю операцию?

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

      ну, например, можно в оффлайне: поддерживаем дерево отрезков на максимум, в которое будем постепенно добавлять Tj. Изначально дерево заполнено минус бесконечностями. Отсортируем карты по возрастанию Bi и будем обрабатывать их в таком порядке. Обработка очередной карты заключается в следующем:
      1. добавим в дерево отрезков все Tj < Bi, т. е. j-му элементу ДО присвоим Tj.
      2. найдем самый правый подходящий запрос. Можно сделать бинпоиском за O(log2K), каждый раз проверяя, попадает ли максимум в отрезкок [Ai;Bi) или спуском по дереву отрезков за O(logK).

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

Can you give the link to the question?

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

    Sorry, haven't link. Can give only photo, but it on the russian language.

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

When we were on a training camp for Bulgarian's junior and senior national teams one morning while we were having breakfast I heard Hristo Venev talking about this problem and he said that he has solved it for full score using BIT(indexes are T-s). I'm not sure about the constraints but the statement was the same. It was a couple of months ago and I still can't solve it and I really want to know the solution. I hope that this post will help someone to solve the problem.

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

The problem is exactly the same as "Fortune Telling 2" from JOI Open Contest 2014. There is a comment which described the solution.