Вам дан массив из N<=10^5 целых чисел в интервале [1,K]. K<=50. Вы должны обработать M<=10^5 запросов 2-х видов :
1 i x — изменить значение i-го числа на x
2 — вывести длину кратчайшего непрерывного подотрезка массива, содержащего все целые числа от 1 до K
...
P. S. Буду рад услышать любой совет и подсказку. Заранее спасибо.
P.P.S Решил, всем спасибо. Сдал решением alexsushin. Даже не понадобились 2 указателя : я поддерживал минимальное подходящее r (то есть сначала просто r присваивал максимуму из t[v * 2 + 1].pref[i] для всех i которых вообще нет в левой части, а потом проходился по отсортированному вектору t[v * 2].suff и "удалял" этот элемент, тогда левая граница нового отрезка — следующий элемент в векторе, и так как я удаляю последнее вхождение элемента на левом подотрезке, то надо пересчитать r = max(r, t[v * 2 +1].pref['элемент который удалил']). Суть в принципе та же, но не нужен дополнительный массив cnt и двигать указатели, а просто пересчет r.
Откуда задача?
Задача с сайта dl.gsu.by
Была на олимпиаде Гомельской области для учащихся 5-7 классов в апреле 2023 года.
P.S если зарегистрируйтесь на сайте для быстрого поиска можно использовать ее id : 236405
Такое чувство, что можно легче, но...
Заметим, что кол-во различных чисел мало
какую структуру обычно используют в таких задачах?
Давай представим числа как битовые маски.
Тогда построим ДО на побитовое Или на отрезке.
Итак, отрезок содержит все числа, когда в его битовой маске все $$$k$$$ битов заединичены.
Т.е. наше Или на этом отрезке даст $$$2^k-1$$$. Наша задача найти такой отрезок минимальной длины.
Давай заново посчитаем наше ДО. Как только в какой-то вершине маска полностью заединичена смотрим на маски детей. У левого есть какие-то нулевые биты, и у правого тоже они есть.
Сделаем бинпоиск по отрезку левого сына, найдя первую маску, что покрывает нулевые биты правого сына (мы можем найти побитовое ИЛИ на отрезке за логарифм), и тоже самое сделаем для правого.
В запросах сначала обновляем ДО на ИЛИ, а потом уже пересчитываем ответ. $$$O( (n+m)*\log^2)$$$
Правильно понимаю, что если побитовое ИЛИ двух детей равны 2 ^ k — 1, то мы спускаемся, как и влево, так и вправо?
Решение, как я понял неправильное, тк не учитываю общие у детей биты.
А так, — нет. Мы уже поднялись из детей и их ИЛИ получилось в 2^k-1. И только потом делаем бинпоиск (или спуск). В любом случае решение неправильное)
Ну просто, не совсем понятно, что значит «Как только в какой-то вершине маска полностью заединичена смотрим на маски детей». Эту вершину надо найти. К тому же это не правда, что таких вершин Log(n)
Ну я вроде в асимптотике учитывал, что их вообще n и для каждого придётся делать бинпоиск для каждой вершины
Спасибо большое за интересные мысли. Но я правильно понимаю, что на один только запрос нам может придётся рассмотреть n вершин?
Чтобы это работало — да. А изначально казалось, что достаточно бинпоиска
Назовем отрезок хорошим, если он содержит все числа от 1 до К.
Будем поддерживать Дерево Отрезков, внутри вершины, отвечающую за отрезок [TL;TR] будем хранить структуру node, которая содержит следующие значения:
ans — минимальная длина хорошего отрезка на [TL;TR].
pref — вектор, содержащий первые вхождения чисел от 1 до К на [TL;TR].
suff — вектор, содержащий последние вхождения чисел от 1 до К на [TL;TR].
Как делать merge двух node {A, B}? Так как мы знаем минимальные хорошие отрезки в A и B, нужно найти минимальный отрезок, у которого левая граница в A, а правая в B. Можно показать, почему существует оптимальный хороший отрезок [L; R], что L принадлежит A.suff, а R принадлежит B.pref.
Доказательство: «Предположим, что R не принадлежит B.pref. Так как отрезок точно проходит через разрез между A и B (т.е. является префиксом B и суффиксом A), то элемент на позиции R встречается не впервые (по определению B.pref), следовательно можно подвинуть правую границу влево и хуже не станет. Доказательство, что L принадлежит A.suff аналогично.»
На основе этого можно написать решение с двумя указателя для поиска этого отрезка и попробовать улучшить через него ans. Достаточно очевидно, как поддерживать pref и suff. Так как мы содержим информацию только о различных числах, то длина pref и suff никогда не превышает K, следовательно каждая часть merge работает за O(K). Получается запрос изменения работает за O(K * log(N)), т.к. мы изменим node лишь в O(Log(N)) вершинах
Большое спасибо. Мне правда пока что непонятно как двумя указателями пытаться пересчитывать ответ (чтобы это за K работало).
Если Вам нетрудно, можете пожалуйста подробнее рассказать про эту часть решения?
Идем 1 указателем с конца A.suff, а 2 указателем с начала B.pref. Можно завести, например, массив cnt[K],
где cnt[i] = сколько раз встречается элемент с значением i.
Когда двигаем 1 указатель с конца A.suff, возможно, одного элемента теперь нет в отрезке, поэтому двигаем 2 указатель в B.pref, чтобы этот элемент снова вернулся и меняем массив cnt.