#114218

Бар у Мо

Темы: [Корневая эвристика (sqrt декомпозиция)]

В баре у Мо дела идут как всегда прекрасно. Чтобы дела шли еще лучше, Мо озадачился вопросом разнообразия сортов пива, которые разливают в его баре. Для составления стратегического плана по улучшению списка сортов пива Мо должен получить ответы на ряд вопросов.

В данный момент у барной стойки сидят $n$ посетителей и у каждого посетителя есть кружка с пивом одного из сортов. Мо пронумеровал посетителей слева направо числами от $1$ до $n$. После этого он пронумеровал сорта пива числами от $1$ до $m$. Далее Мо вспомнил число $k$, которое было рекомендовано в гороскопе на эту неделю. Наконец, Мо составил список из $q$ вопросов, ответы на которые помогут его бизнесу стать еще успешней. В каждом вопросе спрашивается следующее: каково количество сортов пива, которые можно встретить ровно $k$ раз в кружках посетителей с номерами от $l$ до $r$ включительно.

Входные данные

В первой строке даны четыре целых числа $n$, $m$, $q$ и $k$ ($1 \le n, \ q \le 2 \cdot 10^5$, $1 \le m \le 10^6$, $0 \le k \le 3$).

Во второй строке даны $n$ целых чисел $1 \le a_1, \ldots, a_n \le m$ -- номера сортов пива у посетителей.

В следующих $q$ строках заданы по два целых числа $l$ и $r$, которые задают запрос для посетителей с номерами от $l$ до $r$ ($1 \le l \le r \le n$).

Выходные данные

Для каждого запроса выведите в отдельной строке количество сортов пива, которые на отрезке от $l$ до $r$ встречаются ровно $k$ раз.

Примеры

Входные данные

Выходные данные

2
1

#114219

Бар у Мо 2

Темы: [Корневая эвристика (sqrt декомпозиция)]

В баре у Мо дела идут по-прежнему прекрасно. Как известно, чтобы дела шли еще лучше, Мо озадачился вопросом разнообразия сортов пива, которые разливают в его баре. Для составления стратегического плана по улучшению списка сортов пива Мо должен получить ответы на ряд вопросов.

В данный момент у барной стойки сидят $n$ посетителей и у каждого посетителя есть кружка с пивом одного из сортов. Мо пронумеровал посетителей слева направо числами от $1$ до $n$. После этого он пронумеровал сорта пива числами от $1$ до $m$. Далее Мо вспомнил число $k$, которое было рекомендовано в гороскопе на эту неделю. Наконец, Мо составил список вопросов, ответы на которые помогут его бизнесу стать еще успешней. В каждом вопросе спрашивается следующее: каково количество сортов пива, которые можно встретить ровно $k$ раз в кружках посетителей с номерами от $l$ до $r$ включительно.

Мо ответил на все вопросы, но вдруг заметил, что пока он отвечал на вопросы, некоторые посетители выпивали свое пиво и тут же заказывали новую кружку с пивом, возможно другого сорта.

Чтобы проверить правильно ли Мо ответил на все вопросы, напишите программу которая ответит на все вопросы, учитывая все заказы посетителей. Всего в сумме произошло $q$ событий, каждое из которых либо смена кружки пива одним из посетителей или вопрос от Мо.

Входные данные

В первой строке даны четыре целых числа $n$, $m$, $q$ и $k$ ($1 \le n, \ q \le 10^5$, $1 \le m \le 10^6$, $0 \le k \le 3$).

Во второй строке даны $n$ целых чисел $1 \le a_1, \ldots, a_n \le m$ -- номера сортов пива у посетителей.

В следующих $q$ строках заданы события. Каждое событие одного из двух типов:

$1 \ l \ r$ -- вопрос от Мо ($1 \le l \le r \le n$).

$2 \ i \ j$ -- $i$-й посетитель перешел на пиво сорта $j$, ($1 \le i \le n$, $1 \le j \le m$).

Выходные данные

Для каждого запроса первого типа выведите в отдельной строке ответ на него.

Примеры

Входные данные

Выходные данные

2
1

#114304

Расстояние

Темы: [Арифметические алгоритмы]

Рассмотрим следующую операцию, определённую на целых положительных числах. Операция состоит в умножении числа $q$ на простое число $p$, либо в делении числа $q$ на простое число $p$, если $q$ делится на $p$ без остатка. Назовем расстоянием между числами $a$ и $b$ минимальное количество операций, необходимое для того чтобы получить из числа $a$ число $b$. Обозначим расстояние как $d(a, b)$.

Дана последовательность из $n$ положительных чисел $a_1, a_2, ... a_n$. Для каждого индекса $i$ ($ 1 \le i \le n$) необходимо найти индекс $j$, такой что $1 \le j \le n$ и $i \ne j$, и что $d(a_i, a_j)$ минимально.

Входные данные

Первая строка входных данных содержит одно целое число $n$ — количество элементов в последовательности $a$ ($1 \le n \le 100 000$).

В последующих $n$ строках входных данных даны $n$ целых чисел $a_1, a_2, \ldots, a_n$ — элементы последовательности ($1 \le a_i \le 10^{6}$) ($i$-е число в $i + 1$ строке).

Выходные данные

Выведете $n$ строк. В $i$ строке выведете такой минимальный индекс $j$, такой что $1 \le j \le n$ и $i \ne j$, и что $d(a_i, a_j)$ минимально.

Система оценки

В тестах суммарной стоимостью не менее $30$ баллов дополнительно гарантируется что $n \le 1000$, $a_i \le 10000$.

Примеры

Входные данные

Выходные данные

Входные данные

2
1
1

Выходные данные

2
1

#114305

Телепортация_0

Темы: [Алгоритмы на графах] [Обход в ширину]

На дворе $3020$ год. Король Байтазар правит огромной планетарной системой, в которой насчитывается целых $n$ планет. В $3020$ году люди отказались от традиции давать планетам имена и вместо этого используют номера. Дворец Байтазара находится на планете под номером $1$, в то время как его военная база находится на планете под номером $2$. Давным давно для Байтазара был построен портал, соединяющий планеты $1$ и $2$, который позволяет добираться с планеты номер $1$ на планету номер $2$ или обратно за $250$ минут (немногим больше четырёх часов).

С тех пор технологии шагнули далеко вперёд, и современные порталы позволяют добиратся между планетам всего за $1$ час (в $3020$ году в часе всё ещё $60$ минут). Порталы, разумеется, остались двухсторонними. Некоторые из планет уже соединены современными версиями порталов (но не планеты $1$ и $2$ - король Байтазар крайне консервативен). Вообще, уже сейчас возможно добраться от планеты $1$ до планеты $2$ используя имеющиеся новые порталы, но личный портал Байтазара остаётся самым быстрым способом добраться между планетами $1$ и $2$.

Технология быстрой телепортации продолжает своё распространение и Байтазар хочет это поддержать, не желая между тем менять свой личный портал старого типа на новый. При этом, из соображений безопасности Байтазар не хочет, чтобы был способ добраться с планеты $1$ на планету $2$ быстрее, чем его личный портал. Помогите Байтазару. Найдите максимальное число новых порталов, которые можно построить так, чтобы личный портал Байтазара оставался самым быстрым путем перемещения между резиденцией и военной базой.

Входные данные

В первой строке даны два числа $n$ и $m$ ($ 2 \le n \le 40000, 1 \le m \le 1000000$) - количество планет в планетарной системе Байтазара и количество двусторонних порталов нового типа соответственно.

В последующих $m$ строках дано описания порталов. Каждая строка содержит два целых числа $v$ и $u$, ($1 \le v, u \le n$, $v \ne u$), что означает что планеты $v$ и $u$ соединены порталом нового типа.

Гарантируется, что существует способ добраться с планеты $1$ на планету $2$ используя имеющиеся порталы и что такое путешествие займёт строго больше $250$ минут.

Выходные данные

Выведете единственное число $ans$ - наибольшее количество порталов которое можно построить в планетарной системы Байтазара, так чтобы личный портал Байтазара оставался самым быстрым путем перемещения между резиденцией и военной базой.

Система оценки

В тестах суммарной стоимостью не менее $20$ баллов дополнительно гарантируется что $n \le 8$, $m \le 9$.

В тестах суммарной стоимостью не менее $30$ баллов дополнительно гарантируется что $n \le 12$, $m \le 20$.

В тестах суммарной стоимостью не менее $60$ баллов дополнительно гарантируется что $n \le 150$, $m \le 4000$.

Примечание

Иллюстрация к первому примеру:

$\text{[math]}$

Жирными линиями показаны имеющиеся скоростные порталы, в то время как пунктирными линиями показаны те порталы, которые Байтазар может построить, не подвергнув государство опасности и построив при этом максимально возможное количество скоростных порталов.

Примеры

Входные данные

Выходные данные

#114306

Префиксуффикс

Темы: [Алгоритмы на строках] [Z-функция, Префикс-функция]

Строка $s$ назывется префиксом строки $t$, если строка $t$ начинается со строки $s$. Строка $s$ назывется суффиксом строки $t$, если строка $t$ заканчивается на строку $s$.

Назовём две строки $s$ и $t$ циклически эквивалентными, если существует циклический сдвиг, переводящий строку $s$ в строку $t$; другими словами строки $s$ и $t$ циклически эквивалентны тогда и только тогда, когда, строка $s$ может быть получена из строки $t$ путем перемещения некого суффикса строки $t$ в начало строки $t$. Например, строки $ababba$ и $abbaab$ циклически эквивалентны, в то время как строки $ababba$ и $ababab$ нет. В частности, любая строка циклически эквивалентна самой себе.

Дана строка $t$ длины $n$. Требуется найти такой префикс $p$ и такой суффикс $s$ строки $t$, что:

$p$ циклически эквивалентен $s$ (и, как следствие, их длины равны)
длина $p$ не превосходит $\frac{n}{2}$ (то есть $p$ и $s$ не пересекаются в $t$)
длина $p$ максимальна

Входные данные

Первая строка входных данных содержит одно целое число $n$ — длину строки $е$ ($1 \le n \le 1000 000$).

Вторая строка входных данных содержит строку $t$ состоящую из строчных латинких букв.

Выходные данные

Выведите единственное целое число $res$ - наибольшее целое число, такое что ($0 \le res \le \frac{n}{2}$) и $res$ - ый префикс строки $t$ циклически эквивалентен $res$-му суффиксу строки $t$.

Система оценки

В тестах суммарной стоимостью не менее $30$ баллов дополнительно гарантируется что $n \le 500$.

В тестах суммарной стоимостью не менее $50$ баллов дополнительно гарантируется что $n \le 5000$.

В тестах суммарной стоимостью не менее $80$ баллов дополнительно гарантируется что $n \le 200000$.

В тестах суммарной стоимостью не менее $90$ баллов дополнительно гарантируется что $n \le 500000$.

Примеры

Входные данные

15
ababbabababbaab

Выходные данные