Заметим, что игра закончится только тогда, когда фишка находится в правом верхнем углу (иначе можно сдвинуть её на $$$1$$$ клетку вправо или вверх). За все ходы фишка сдвинется на $$$n - 1$$$ вправо и на $$$m - 1$$$ вверх, значит, суммарная длина всех ходов равна $$$n + m - 2$$$ (длина хода — на сколько сдвинулась фишка за ход). Так как длина любого хода нечётна, то после любого хода Бурёнки сумма длин будет нечётна, а после любого хода Тони чётна. Значит, мы можем узнать, кто сделал последний ход в игре, посмотрев на $$$(n + m - 2) \operatorname{mod} 2 = (n + m) \operatorname{mod} 2$$$. При $$$(n + m) \operatorname{mod} 2 = 0$$$ побеждает Тоня, иначе — Бурёнка.

Сложность решения — $$$O(1)$$$.

Заметим, что от числа $$$k$$$ нам нужен только остаток по модулю $$$4$$$, поэтому возьмём $$$k$$$ по модулю и будем считать, что $$$0 \leq k \leq 3$$$.

Если $$$k = 0$$$, то ответа нет, так как тогда произведение чисел в каждой паре должно делиться на $$$4 = 2^2$$$, то есть произведение всех чисел от $$$1$$$ до $$$n$$$ должно делиться на $$$2^{\frac{n}{2} \cdot 2} = 2^n$$$, но степень вхождения $$$2$$$ в эту сумму равно $$$\lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{4}\rfloor$$$, что меньше $$$n$$$.

Если $$$k = 1$$$ или $$$k = 3$$$, то сделаем все пары вида $$$(i, i + 1)$$$, где $$$i$$$ — нечётное. Тогда $$$a + k$$$ будет чётным в каждой паре, так как $$$a$$$ и $$$k$$$ нечётные, а так как $$$b$$$ тоже чётное, то произведение будет делится на $$$4$$$.

Если $$$k = 2$$$, то сделаем то же разбиение на пары, но во всех парах, где $$$i + 1$$$ не делится на $$$4$$$, поменяем числа местами (то есть сделаем $$$a = i + 1$$$ и $$$b = i$$$). Тогда в парах, где $$$i + 1 \operatorname{mod} 4 = 0$$$, $$$b$$$ делится на $$$4$$$ (значит, и произведение тоже), а в остальных $$$a + k$$$ делится на $$$4$$$ (так как $$$a$$$ и $$$k$$$ имеют остаток $$$2$$$ по модулю $$$4$$$).

Сложность решения — $$$O(n)$$$.

Кто бы побеждал в поединках, если бы самый сильный спортсмен был бы первым в очереди?

После какого числа раундов самый сильный спортсмен гарантированно окажется в начале очереди?

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

Заметим, что после того, как самый сильный спортсмен окажется в начале очереди, выигрывать будет только он. Самый сильный спортсмен окажется в начале очереди не более, чем после $$$n$$$-го раунда. Промоделируем первые $$$n$$$ раундов, если в $$$i$$$-м раунде победил $$$j$$$-й спортсмен, то запишем для него номер $$$i$$$. Теперь для ответа на запрос $$$(i, k)$$$ достаточно бинпоиском найти число побед $$$i$$$-го спортсмена в раундах с номерами $$$j \leq k$$$, а если $$$k > n$$$, и сила $$$i$$$-го спортсмена равна $$$n$$$, то к ответу нужно прибавить ещё $$$k - n$$$.

Сложность решения — $$$O(n + q log n)$$$.

Существует ответ, где потраченное время минимально и длины всех взятых отрезков 1 и 2. Ведь, отрезок длины $$$l, r, x$$$ можно представить как $$$\lceil \frac{r-l+1}{2} \rceil$$$ отрезков длины 2 и 1, а точнее $$$[l, l + 1, x], [l + 2, l + 3, x], \ldots, [r, r, x]$$$(или $$$[r-1, r, x]$$$ если $$$(l - r + 1)$$$ четное).

Заметим, что если для $$$l, r$$$ выполнено $$$a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r} = 0$$$, то мы можем заполнить нулями подотрезок $$$l, r$$$ за $$$r-l$$$ секунд запросами $$$[l, l+1, a_l], [l+1, l+2, a_l \oplus a_{l+1}], ... [r-1, r, a_l \oplus a_{l+1} \oplus \ldots \oplus a_r]$$$.

Заметим, что если отрезок длины 2 пересекается с отрезком длины 1, их можно менять на 2 отрезка длины 1.

Из этого всего следует, что ответ представляет из себя отрезки длины 1 и куски покрытые отрезками длины 2. Тогда легко видеть, что ответ представляет из себя $$$n - $$$ (максимальное количество непересекающихся подотрезков с ксором 0). это количество можно посчитать динамическим программированием или жадно.

В начале проверим, что число $$$n$$$ (сумма всех $$$c_i$$$) представимо в виде суммы какого-то префикса чисел Фибоначчи, в противном случае выведем ответ NO.

Давайте попробуем набирать ответ жадно, идя от больших чисел Фибоначчи к меньшим. Для очередного числа Фибоначчи возьмём букву с наибольшим числом вхождений в строку из числа тех, которые не равны предыдущей взятой букве (для избежания появления двух соседних блоков из одной и той же буквы, чего быть не может). Если вхождений этой буквы меньше, чем это число, то ответ NO. Иначе поставим букву на это число Фибоначчи и вычтем его из числа вхождений этой буквы.Если мы смогли набрать все числа Фибоначчи, то ответ YES.

Почему же жадное решение работает? Пусть на данном шаге нужно взять $$$F_i$$$ (я буду говорить взять число из $$$c_t$$$ это будет значить взять $$$F_i$$$ букв вида $$$t$$$) , посмотрим на максимальное $$$c_x$$$ сейчас, если его нельзя представить как сумму несоседних чисел Фибоначчи до $$$F_i$$$, то ответ нет. Можно доказать, что если $$$c_x > F_{i+1}$$$, то представить $$$c_x$$$ невозможно.

Если на шаге ровно одно число больше или равно $$$F_i$$$, тогда вариант взять нужное число всего один, поэтому жадное решение работает.

Если существует два таких числа и они равны, то вариант взять нужное число ровно один с точностью до перестановки букв. Жадник опять работает.

Если же есть $$$c_j \geq F_i, c_x \geq F_i, j \ne x$$$, то заметим, что большее из чисел $$$c_j, c_x$$$ будет больше $$$F_i$$$, если мы не возьмем его, то на следующем шаге это число будет больше $$$F_{i+1}$$$($$$i$$$ станет на 1 меньше), по доказанному выше ответа не будет, значит, брать большее из чисел всегда оптимально.

Давайте заметим, что ответ для $$$k=x$$$ и $$$k=\gcd(x, n)$$$ одинаков.

Действительно, для числа $$$k$$$ мы посетим числа c индексами $$$s + ik \mod n$$$ для $$$i$$$ от $$$0$$$ до $$$n-1$$$ включительно, из этого можно видеть, что индекс $$$i$$$-го числа совпадает с индексом $$$i + \frac{n}{\gcd(k, n)}$$$, причем если смотреть на два индекса, разница между которыми равна $$$l$$$ и $$$l < \frac{n}{\gcd(k, n)}$$$, то они различны, так как $$$k \cdot l \mod n \neq 0$$$, следовательно, ответ представляет из себя (сумму чисел с индексами $$$s + ik \mod n$$$ для $$$i$$$ от $$$0$$$ до $$$\frac{n}{\gcd(k, n)}-1$$$) $$$\cdot \gcd(k, n)$$$.

Теперь давайте докажем, что первые $$$\gcd(k, n)$$$ чисел одинаковы для $$$(s, x)$$$ и $$$(s, \gcd(x, n))$$$, заметим, что подходят только те индексы, которые имеют такой же остаток при делении на $$$\gcd(x, n)$$$ как и $$$s$$$, но таких индексов только $$$\frac{n}{\gcd(k, n)}$$$, а мы доказали, что у нас должно встречаться $$$\frac{n}{\gcd(k, n)}$$$ различных индексов, значит все они представлены по разу, следовательно ответ для $$$k=x$$$ и $$$k=\gcd(x, n)$$$ одинаков, ведь сумма состоит из одинаковых чисел. Ч.Т.Д.

Значит, нам нужно рассматривать только $$$k$$$ являющиеся делителями $$$n$$$, это уже заходит, если написать, например, дерево отрезков, но мы не хотим писать дерево отрезков, поэтому идем дальше, докажем, что для $$$k_1 = x$$$, ответ меньше или равен, чем для $$$k_2 = x \cdot y$$$ если $$$k_1$$$ и $$$k_2$$$ делители $$$n$$$, почему это так?

Заметим, что для числа $$$k$$$ ответ бьется на $$$\gcd(k, n)$$$ групп чисел, так что в каждой группе ровно $$$\frac{n}{\gcd(k, n)}$$$ и каждое число входит ровно в одну группу, причем для разных $$$s$$$ ответ будет выглядеть как (сумма в группе которой принадлежит $$$s$$$) $$$\cdot \gcd(k, n)$$$.

Посмотрим, на ответ для оптимального $$$s$$$ для $$$k_1$$$ назовем множество при котором он достигается $$$t$$$, заметим, что в $$$k_2$$$ для разных $$$s$$$ есть $$$m$$$ независимых множеств, которые являются подмножествами $$$t$$$. Пусть $$$m_i$$$ сумма в $$$i$$$-м множестве. Теперь заметим, что нам нужно доказать $$$max(m_1, m_2, \ldots, m_y) * y \geq m_1 + m_2 + \ldots m_y$$$ это верно для любых $$$m_i$$$, легко видеть. Ч.Т.Д.

Значит нужно перебирать делители вида $$$\frac{n}{p}$$$ где $$$p$$$ простое, теперь это можно сдать с сетом. ура!

Для делителя $$$d$$$ предлагается хранить ответы для всех пар $$$(s, d)$$$, где $$$s \le \frac{n}{d}$$$ и максимум среди них, их можно посчитать изначально за $$$O(n log n)$$$ для одного $$$d$$$, каждый запрос это изменение одного из значений, это можно сделать за $$$O(log n)$$$.

Сложность авторского решения $$$O(6 \cdot n \operatorname{log}(n))$$$, где 6 это максимальное количество различных простых делителей числа $$$n$$$.

Давайте построим дерево рекурсивно начав с отрезка $$$[1, n]$$$, на каждом шаге будем выбирать корнем поддерева $$$v = \operatorname{argmax}([p_l, p_{l+1} \ldots, p_r]) + l - 1$$$, затем рекурсивно построим деревья для подотрезков $$$[1, v-1], [v+1, n]$$$ если они не пустые, затем создадим ребра из корня в корни этих поддеревьев. То что мы получили называется декартовым деревом по массиву. Дальше в разборе будет упоминаться именно это дерево.

Легко видеть, что декартовы деревья по массивам совпадают тогда и только тогда, когда эти массивы похожи. Тогда необходимое и достаточное условие для того, чтобы массив $$$a$$$ был похож на $$$p$$$ это то, что для любой пары $$$u, v$$$ такой, что $$$u$$$ находится в поддереве $$$v$$$, выполнено $$$a_v > a_u$$$, другими словами $$$a_v$$$ максимум среди чисел в поддереве вершины $$$v$$$.

Назовем позицию $$$i$$$ изначально пустой, если изначально $$$a_i = 0$$$

Назовем массив $$$a$$$ почти похожим на $$$p$$$ если для любой пары $$$u, v$$$ такой, что $$$u$$$ находится в поддереве $$$v$$$, выполнено $$$a_v > a_u$$$ или обе позиции $$$u$$$, $$$v$$$ изначально пустые.

Докажем, что если существует способ заполнить пропуски в $$$a$$$, чтобы получить почти похожий на $$$p$$$ массив, то существует и способ заполнить пропуски, чтобы получить похожий.

Действительно, давайте посмотрим на почти похожий на $$$p$$$ массив $$$a$$$. пройдемся по дереву рекурсивно начиная с корня. На шаге с вершиной $$$v$$$ сначала запустимся рекурсивно от всех детей $$$v$$$, теперь для них верно, что максимумы их поддеревьев в них, посмотрим на максимального ребенка $$$v$$$, пусть это $$$u$$$, тогда если $$$a_v > a_u$$$, то всё хорошо, иначе $$$a_v < a_u$$$ заметим, что $$$v$$$ является изначально пустой позицией, ведь для всех изначально не пустых позиций верно, что они являются максимумами в своих поддеревьях (это легко видеть подставив в определение), a $$$v$$$ не является. Заметим, что $$$u$$$ является изначально пустой позицией. ведь иначе, мы ни разу не изменили $$$a_v$$$ и $$$a_u$$$, следовательно в изначальном почти похожем на $$$p$$$ массиве $$$a$$$ выполнялось $$$a_v > a_u$$$ противоречие. значит $$$v, u$$$ изначально пустые, мы можем выполнить $$$swap(a_v, a_u)$$$ и всё будет выполняться.

После выполнения этого алгоритма мы изменили только изначально пустые элементы и получили $$$a$$$ похожую на $$$p$$$. ЧТД

Как проверить существование почти похожего на $$$p$$$ массива? Назовем числом $$$r_i$$$ минимум среди всех чисел $$$a_v$$$ таких, что $$$i$$$ находится в поддереве $$$v$$$. Назовем числом $$$l_i$$$ максимум среди всех чисел $$$a_v$$$ таких, что $$$v$$$ находится в поддереве $$$i$$$. легко видеть, что $$$a$$$ является почти похожим на $$$p$$$ если для всех $$$i$$$ выполняется, $$$l_i < a_i < r_i$$$.

Это звучит невероятно хорошо. Значит, всё что нам нужно это найти паросочетание множества $$$S_d$$$ и отрезков вида $$$[l_i, r_i]$$$ для $$$i$$$ являющихся изначально пустыми. Теперь легко доказать (пусть для $$$d_1$$$ ответ да, ответ для $$$d_2$$$ мы не знаем, попробуйте посмотреть на чередующийся путь из $$$d_1$$$ в $$$d_2$$$ в парососчетании, легко видеть, что если такой путь есть, то для $$$d_2$$$ ответ да, иначе, нет. Если посмотреть на структуру паросочетания точек с отрезками, можно увидеть, что чередующийся путь существует для непрерывного отрезка значений $$$d_2$$$), что подходящие $$$d$$$ являются непрерывным отрезком. границы можно найти бинарным поиском или два раза набирав жадно.

Асимптотика решения $$$O(n \operatorname{log} n)$$$ или $$$O(n \operatorname{log}^2 n)$$$

Заведем две перестановки $$$p$$$ длины $$$n$$$ и $$$q$$$ длины $$$m$$$. Изначально обе перестановки тождественны. Для операции $$$1\, i \, j$$$, будем выполнять $$$\operatorname{swap}(p_i, p_j)$$$, для операции $$$2\, i\, j$$$ будем выполнять $$$\operatorname{swap}(q_i, q_j)$$$. Легко видеть, что после выполнения всех операций в позиции $$$i, j$$$ будет стоять $$$a_{p_i,q_j}$$$.

Теперь нужно найти подходящие перестановки $$$p, q$$$, чтобы $$$a_{p_i,q_j} = b_{i, j}$$$.

Давайте посмотрим на двудольный граф, где первая доля это строки, а вторая это столбцы. Пусть если $$$a_{i, j} \ne 0$$$, то из $$$i$$$ есть неориентированное ребро в $$$j$$$ цвета $$$a_{i, j}$$$. если построить такой же граф для $$$b$$$, то нам нужно проверить на изоморфность два двудольных графа каждое ребро которых имеет цвет, причем как мы помним по условию вершине не могут быть инцедентны 2 ребра одного цвета. Назовем их графом $$$a$$$ и графом $$$b$$$.

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

Пусть $$$n < m$$$ иначе давайте поменяем $$$n$$$ и $$$m$$$ местами. Давайте попробуем сопоставить элементы массива $$$a$$$ элементам массива $$$b$$$. Давайте пройдемся по индексам от $$$1$$$ до $$$n$$$. Пусть сейчас мы выбираем, какую пару из $$$b$$$ выбрать для $$$i$$$-ой вершины первой доли графа $$$a$$$. Если мы уже нашли пару раньше, пропустим шаг, иначе давайте переберем подходящий вариант для пары среди всех еще не имеющих пары вершин первой компоненты $$$b$$$, таких не больше $$$n$$$, после сапостовления вершин, рёбра тоже сопоставляются однозначно(ведь не существует 2 ребер разных цветов), давайте, тогда запустим подставление рекурсивно для ребер(если мы сопоставили вершину $$$v$$$ вершине $$$u$$$ и из $$$v$$$ есть ребро цвета $$$x$$$ в $$$i$$$, а из $$$u$$$ есть ребро $$$x$$$ в $$$j$$$, то легко доказать, что в ответе $$$i$$$ будет сопоставлено с $$$j$$$), а значит мы восстановим всю компоненту. Пусть сумма числа вершин и числа ребер в компоненте это $$$k$$$, тогда мы выполним не больше, чем $$$n \cdot k$$$ действий для восстановления компоненты.

по перестановкам получить последовательность обменов это дело техники, его я объяснять не буду, но это отдельная функция в авторском решении вы разберетесь.

суммарно наше решение работает за $$$O(n(n \cdot m + n + m))$$$ изи за $$$O(min(n, m)(n \cdot m + n + m))$$$, где $$$n \cdot m + n + m$$$ суммарное число вершин и ребер во всех компонентах.

если вы чего-то не поняли, задавайте вопросы!

Вы можете выбрать одну лучшую задачу, или не выбирать, если считаете, что такой нет.