После отборочного тура Технокубка вы нашли шахматную доску размера n x m. Но вы не собираетесь играть в шахматы, так как вам опять предстоит решить задачу по программированию. А именно, вам нужно обрабатывать 3 вида запросов: 1xy — поставить слона в клетку (x;y). Гарантируется, что клетка пуста на момент поступления запроса. 2xy — убрать слона из клетки (x;y). Гарантируется, что в клетке стоит слон на момент поступления запроса. 3xy — рассмотрим всех слонов, которые сейчас стоят на доске. Для каждого вычислим минимальное число ходов, чтобы достичь клетки (x;y) (если слон никогда не сможет достичь клетки, положим его равным бесконечности). Среди всех этих чисел необходимо найти минимальное. Система оценки Группа тестов Дополнительные ограничения Баллы Необходимые группы 1 n,m,q≤30 12 — 2 n=m 10 — 3 n⋅m⋅q≤107 28 1 4 (n+m)⋅q≤107 15 1,3 5 — 35 1−4 Формат входных данных Первая строка содержит два целых числа n и m — размеры доски (1≤n,m≤109). Вторая строка содержит одно целое число q — количество запросов, которые необходимо обработать (1≤q≤2⋅105). Каждая из следующих q строк содержит 3 целых числа t,x,y — тип запроса и координаты клетки доски (1≤t≤3,1≤x≤n,1≤y≤m). Формат выходных данных Выведите ответ на каждый запрос третьего типа в новой строке. Если ответ равен бесконечности — выведите −1. напиши код на джава или пайтоне

Пояснение к решению (Цель: понять) Идея простая: на доске находятся слоны. Чтобы ответить на запрос типа 3, нам не нужно учитывать конкретные пути слонов, их блокировки и т. п. Мы считаем минимальное число ходов в классическом бес Obstacles варианте bishops: - Если слон уже стоит в целевой клетке — 0 ходов. - Если целевая клетка лежит на одной диагонали с хотя бы одним слоном — 1 ход. - Если ни на одной диагонали, но слон имеет ту же цветовую клетку, что и целевая — 2 хода. - Если никто из слонов не имеет нужного цвета — бесконечность (выводим -1). Для эффективной поддержки динамики (добавление/удаление слонов) используем следующие структуры: - множество occupied для хранения занятых клеток. - словарь diag_sum для подсчета количества слонов на каждой главной диагонали типа x+y (диагональ \). - словарь diag_diff для подсчета слонов на каждой вторичной диагонали типа x-y (диагональ /). - массив color_cnt размером 2 для количества слонов на каждой цветной клетке (цвет определяется как (x+y) % 2). Обновления за O(1) и запросы за O(1) в среднем: - Добавление слона: поместить в occupied, увеличить diag_sum[x+y], diag_diff[x-y], color_cnt[(x+y)&1]. - Удаление слона: убрать из occupied, уменьшить соответствующие счетчики. - Запрос типа 3: если целевая клетка занята — 0; иначе если на одной из диагоналей есть слон — 1; иначе если есть слон той же цветности — 2; иначе -1. Код на Python 3: ```python import sys def main(): data = list(map(int, sys.stdin.buffer.read().split())) if not data: return it = iter(data) n = next(it) # размер доски (не используется напрямую) m = next(it) q = next(it) occupied = set() # занятые клетки (x, y) diag_sum = {} # диагональ x+y -> количество слонов на ней diag_diff = {} # диагональ x-y -> количество слонов на ней color_cnt = [0, 0] # color_cnt[0] — слоны на тёмных клетках, color_cnt[1] — на светлых out_lines = [] for _ in range(q): t = next(it) x = next(it) y = next(it) if t == 1: # поставить слона в (x, y) occupied.add((x, y)) s = x + y d = x - y diag_sum[s] = diag_sum.get(s, 0) + 1 diag_diff[d] = diag_diff.get(d, 0) + 1 color_cnt[(s & 1)] += 1 elif t == 2: # убрать слона из (x, y) occupied.remove((x, y)) s = x + y d = x - y cnt = diag_sum.get(s, 0) if cnt <= 1: diag_sum.pop(s, None) else: diag_sum[s] = cnt - 1 dcnt = diag_diff.get(d, 0) if dcnt <= 1: diag_diff.pop(d, None) else: diag_diff[d] = dcnt - 1 color_cnt[(s & 1)] -= 1 else: # запрос типа 3: минимальное число ходов от всех слонов до (x, y) if (x, y) in occupied: out_lines.append("0") else: s = x + y d = x - y if diag_sum.get(s, 0) > 0 or diag_diff.get(d, 0) > 0: out_lines.append("1") elif color_cnt[(s & 1)] > 0: out_lines.append("2") else: out_lines.append("-1") sys.stdout.write("\n".join(out_lines)) if __name__ == "__main__": main() ``` Сложность: - Временная: каждую операцию можно обработать за O(1) в среднем. - Память: O(number_of_bishops) в худшем случае, плюс структуры для диагоналей и цветов. Подходит для q до 2e5 и любых n, m до 1e9.