Дается задача:
Дается 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
Несколько подсказок:
Найдем для каждой карты ее состояние после всех запросов.
Пусть, для определенности, Ai < Bi (в противном случае все аналогично). Тогда найдем последний запрос, для которого Ai < = Tj < Bi. После выполнения такого запроса карта будет лежать стороной Bi. Дальше останется посчитать, сколько после найденного запроса есть запросов с T ≥ Bi — столько раз нужно перевернуть карту после этого.
А как найти такую последнюю операцию?
ну, например, можно в оффлайне: поддерживаем дерево отрезков на максимум, в которое будем постепенно добавлять Tj. Изначально дерево заполнено минус бесконечностями. Отсортируем карты по возрастанию Bi и будем обрабатывать их в таком порядке. Обработка очередной карты заключается в следующем:
1. добавим в дерево отрезков все Tj < Bi, т. е. j-му элементу ДО присвоим Tj.
2. найдем самый правый подходящий запрос. Можно сделать бинпоиском за O(log2K), каждый раз проверяя, попадает ли максимум в отрезкок [Ai;Bi) или спуском по дереву отрезков за O(logK).
Can you give the link to the question?
Sorry, haven't link. Can give only photo, but it on the russian language.
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.
The problem is exactly the same as "Fortune Telling 2" from JOI Open Contest 2014. There is a comment which described the solution.