Помогите решить задачу

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Дается задача:
Дается 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

Комментарии (8)

Написать комментарий?

Alex_2oo8

9 лет назад, # |

+10

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

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

→ Ответить

NuM

+12

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

Bayan

9 лет назад, # ^ |

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

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

hereicomewf

Can you give the link to the question?

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

P_Nyagolov

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.

.o.

+16

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

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