Тема: Timus 1003
Объясните идею решения pls.
Как в этой задаче вообще прикрутить непересекающиеся множества?
Re: Timus 1003
Ну ее необязательно решать через непересекающиеся множества. Например можно так:
Бин поиском будем искать ответ, то есть номер первого ложного высказывания. Для каждой итерации
строим граф из первых высказываний. Ребро идет между стартом и финишом высказывания, вес либо 0, либо 1.
теперь ясно что если в этом графе есть цикл нечетной длины, то было ложное высказывание, иначе нет.
Re: Timus 1003
Если решать непересекающимися множествами, то элементами этих множеств будут куски последовательности от начала до i-ого символа. Для каждого элемента храним четность куска последовательности между ним и его предком. При добавлении запроса, объединяем два соответствующих элемента(если они в разных множествах), иначе проверяем, сходится ли четность если идти по нашему дереву и четность, которую нам сообщили. И не забываем использовать эвристику сжатия путей.
Как-то так;)
Re: Timus 1003
2rf,
а что такое эвристика сжатия путей? когда сдавал эту задачу, ни о чем подобном не подозревал)).
вообще у меня множества хранились так: (главный элемент и его координата, список всех эт-тов связанных с главным, их координаты и четность относительно главного элемента).
Объединение в сумме за O(N log N), время ответа на запрос для эл-тов одного множества - O(1)
Джеймс Гослинг с нами!