Задача A. Занимательная игра

Недавно Айдос изучая культуру древних народов горных местностей, обнаружил одну очень занимательную игру. Как верили создатели этой игры, она играла очень важную роль в культуре и помогала развивать дедуктивное мышление людей всех возрастов. Айдос проникся интересностью игры и решил перевести ее на современный лад. Вот, что у него получилось. Изначально вам дается неориентированный граф с $n$ вершинами и $m$ ребрами. У каждой вершины $v$ есть значение $a_v$. Предлагается произвести над этим графом $q$ операций. Операции могут быть четырех типов:

1. Добавить ребро между существующими вершинами
2. Удалить существующее ребро из графа
3. Изменить значение одной вершины
4. Среди соседей заданной вершины найти $k$-ю по значению вершину.

Замечание. В графе могут быть кратные ребра и не гарантируется, что граф связный. Первая строка входных данных содержит три целых чисел $n, m, q$ через пробел — количество вершин, ребер и операций $(1 <= n, m, q <= 2 \cdot 10^5)$. Вторая строка содержит $n$ целых чисел $a_1, a_2, ..., a_n$ через пробел — значения вершин $(1 <= a_i <= 10^9)$. Следующие $m$ строк содержат описания ребер графа, по два целых числа $u, v$ в каждой строке — неориентированное ребро между вершинами $u$ и $v$ $(1 <= u, v <= n)$. В каждой из следующих $q$ строк содержатся описания запросов. Каждое описание соответствует одному из следующих видов:

• 1 u v — добавить ребро между вершинами $u$ и $v$.
• 2 u v — удалить ребро между вершинами $u$ и $v$. Если их несколько, то удаляется только одно ребро.
• 3 u x — поменять значение вершины $u$ на $x$.
• 4 u k — выведите номер вершины по следующему правилу: отсортируйте соседние вершины $u$ сначала по значению вершин, затем по номеру (оба параметра — по неубыванию). Из отсортированного списка выведите $k$-ю вершину $(1 <= u, v <= 2 \cdot 10^5, 1 <= x <= 10^9)$.

На каждый запрос типа 4 выведите в новой строке номер вершины согласно требованиям в запросе. Данная задача содержит шесть подзадач:

1. $1 <= n, q <= 100$. Оценивается в 6 баллов.
2. $1 <= n, q <= 10000$, также в этой подзадаче нет второго типа запроса. Оценивается в 7 баллов.
3. $1 <= n, q <= 50000$. Оценивается в 22 баллов.
4. $1 <= n, q <= 200000$, $k=1$, также в этой подзадаче нет третьего типа запроса. Оценивается в 9 баллов.
5. $1 <= n, q <= 200000$, также в этой подзадаче нет третьего типа запроса. Оценивается в 12 баллов.
6. Ограничения из условия. Оценивается в 43 баллов.

Вход

3 2 8
3 1 2
1 2
2 3
4 2 1
4 2 2
1 1 3
4 3 2
3 1 2
4 3 2
2 1 3
4 3 1

Ответ

3
1
1
1
2

Задача B. Array

Дан массив $a$ длины $k$. Так же, имеются $n$ массивов длины $k$. Массив $x$ называется хорошим, если существует перестановка $p$ длины $k$, такая что для каждого $i$ $(1 <= i <= k)$ выполняется $x_{p_i} \equiv 0 \pmod{a_i}$. Вам необходимо посчитать количество пар $(l, r)$ $(1 <= l <= r <= n)$, таких что количество хороших массивов в отрезке больше чем нехороших. В первой строке входных данных даются числа $n$ и $k$ $(1 <= n <= 10^5, 1 <= k <= 20)$. Во второй строке входных данных даётся массив $a$ длины $k$ $(1 <= a_i <= 10^9)$. В следующих $n$ строк даются массивы длины $k$, где в $i$-ой содержится массив $b_i$ $(1 <= b_{ij} <= 10^9,$ где $1 <= i <= k)$. В единственной строке выходных данных выведите одно число - ответ на задачу. Данная задача содержит четыре подзадачи:

1. $1 <= n <= 1000, k = 1$. Оценивается в $15$ баллов.
2. $1 <= n <= 1000, 1 <= k <= 8$. Оценивается в $19$ баллов.
3. $1 <= n <= 100, 1 <= k <= 20$. Оценивается в $31$ баллов.
4. $1 <= n <= 10^5, 1 <= k <= 8$. Оценивается в $35$ баллов.

Вход

3 1
2
1
2
2

Ответ

4

$a \equiv 0 \pmod{b}$ - означает что число $a$ делится на $b$ без остатка. В первом тестовом примере, пары $(1, 1)$ и $(1, 2)$ не входят в ответ, так как в одном количество хороших массивов в одном равно $0$ $(0 <= 1)$, а во втором равно $1$ $(1 <= 1)$.

Задача C. Маглы наступают

Интернет в мире представляется в виде $n$ вершин и $n - 1$ ребер, каждое ребро соединяет две вершины, и возможно добраться из каждой вершину в каждую, передвигаясь по ребрам. В каждой вершине живет Волшебник. Волшебники — очень дружелюбные существа, но они могут существовать только парами. 2 Волшебника являются парой, если они находятся в соседних вершинах и решили быть парой. У Волшебника не может быть большой одной пары. Маглы решили заблокировать некоторые вершины дерева, а заодно и забрать Волшебников, живущих в них. Каждая блокировка представляет собой $k$ вершин дерева, которые будут заблокированы. Из каждой заблокированной вершины Маглы забирают Волшебника. После блокировки наступает паника и Волшебники ищут себе пару. Если хотя бы один Волшебник (среди тех, кого не забрали) не найдет себе пару, наступает Хаос. Обратите внимание, Волшебники разбиваются на пары так, чтобы образовать как можно количество пар. У Волшебников есть $q$ предположений того — какие вершины будут блокировать. И на каждый из этих предположений, Волшебникам интересно, будет ли Хаос если случится такая блокировка. В первой строке входных данных дается два числа $n$, $q$ ($1 <= n, q <= 5*10^5$) — количество вершин и количество предположений блокировок соответственно. В следующих $n-1$ строках даются два числа $u$, $v$ ($1 <= u, v <= n$) — вершины, между которыми есть ребро. В следующих $q$ строках подаются описания блокировок в следующем виде: $k, a_1, a_2, \dots, a_k$ $(0 <= k <= n, 1 <= a_i <= n)$ — количество и номера заблокированных вершин. Выведите $q$ чисел, разделенных пробелами. Для каждой блокировки в порядке входных данных выведите $1$, если все Волшебники смогут разбиться на пары (Хаос не наступит), и $0$, если нет (Хаос наступит). Определим $sum(k)$ как суммарное количество вершин во всех блокировках. 1. $1 <= n, q, sum(k) <= 3000$, в дереве нет вершин, у которых больше 2 соседей. Оценивается в $13$ баллов. 2. $1 <= n, q, sum(k) <= 3000$. Оценивается в $17$ баллов. 3. $1 <= n, q, sum(k) <= 100000$. Оценивается в $22$ баллов. 4. $1 <= n, q, sum(k) <= 100000$. $k_i <= 1$. Оценивается в $19$ баллов. 5. $1 <= n, q, sum(k) <= 500000$. Оценивается в $29$ баллов. Вход

3 3
1 2
2 3
1 1
1 2
1 3

Ответ

1 0 1

После блокировки первой вершины или третьей вершины, остаются лишь 2 вершины, которые связаны ребром и поэтому могут образовать пару, что и делают. В случае удаления 2ой вершины, даже если Волшебники хотят образовать пару, они не могут, так как не связаны прямым ребром.