Я подумал над задачей, и на мой взгляд, я знаю линейное решение даже для случая с диагональю.

Если конкретно, есть матрица N x N, и в ней стоят числа. При этом N чисел встречаются в матрице ровно по одному разу (для диагонали), а ещё N*(N-1) разбиваются на пары одинаковых (для парных по симметрии элементов). Нужно за минимальное количество swap-ов сделать симметричную матрицу.

Во-первых, заметим, что диагональные элементы точно должны попасть на диагональ, причём в любом порядке. Буду дальше называть диагональные элементы "дырками", по сути они все взаимозаменяемы. Тогда: 1) Дырки, которые уже на диагонали, трогать не следует. (смотрим на цикл этой дырки: следующий элемент в цикле тоже на диагонали -> можно убрать дырку из цикла, будет на 1 swap меньше) 2) Есть K дырок вне диагонали, и K недырок на диагонали. Утверждается, что достаточно их как-то друг другу сопоставить и сделать по этому сопоставлению K swap-ов изначально, а потом решить задачу без задействования диагонали. (смотрим на цикл с произв. дыркой: видим, что можно сделать swap её со следующим элементов в цикле, что ислючает её из цикла и делает неподвижной)

Теперь разберёмся, как решать задачу без диагонали. У нас есть N*(N-1)/2 пар симметричных клеток. Очевидно, какая клетка снизу диагонали, а какая сверху, значения не имеет: т.е. это неупорядоченные пары. Давайте числа в клетках считать вершинами графа, а симметричные пары — неориентированными рёбрами графа. Получается, что конфигурация матрицы определяет граф, в котором у всех вершин степень 2, а значит он является набором независимых циклов. Следует заметить, что эти циклы уже не то же самое, что обычные циклы в перестановках. Они, например, неориентированные =)

Так вот: минимальное количество swap-ов равно (V — С), где V — количество вершин, а C — количество циклов (включая петли). Видимо, лучше всего это доказывать так, как предлагал Лёша, т.е. так же как это делают на лекциях по алгебре для перестановок. Нужно доказать, что один swap произвольной пары элементов не увеличить количество циклов больше, чем на один. Я попробовал, у меня получилось так: 1) Если делать swap клеток из разных циклов, то эти циклы сливаются (C -= 1). 2) Если делать swap клеток из одного цикла, то либо часть цикла разворачивается (C не изм), либо цикл разбивается на два (C += 1). Это позволяет легко решить задачу без диагонали.

Теперь вспомним про диагональ, однако будем считать, что её нет =) Просто есть K пустых мест в нашей бездиагональной матрице, и K недостающих элементов, которые мы должны расставить по пустым местам перед решением основной задачи. Естественно, эта начальная расстановка потребует от нас K операций, но это число никак не зависит от того, что куда мы поставим, так что в начальной расстановке у нас полная свобода. Нужно выбрать, что куда ставить, так, чтобы максимизировать количество циклов в нашем графе.

Если смотреть на рёбра графа, то они делятся на три типа: 1) Полностью определённые рёбра между двумя конкретно заданными вершинами. 2) Полуопределённое ребро из конкретной вершины в пока непонятно какую: какое число мы воткнём в соотв. пустую клетку матрицы, такой и будет второй конец этого ребра. 3) Неопределённые рёбра, у которых не указана ни одна из концевых вершин — это симметричная пара пустых клеток. Начальное распихивание K недостающих элементов в пустые клетки матрицы соответствует доопределению концов всех рёбер таким образом, чтобы у каждой вершины была степень 2. При этом нам хочется максимизировать количество циклов после доопределения.

Если смотреть на вершины, они могут иметь степени 0, 1 или 2. По вершинам можно сказать, что граф состоит из: 1) Циклы. С ними ничего делать нельзя и не надо. 2) Цепи. При этом каждый конец цепи может быть одного из двух типов: а) с выходящим полуопределённым ребром (т.е. заканчивается на симметричной паре с пустой клеткой) б) без выходящего полуопределённого ребра (заканчивается на симметричной паре без пустых клеток, но дальше продолжить нельзя) В частности, бывают цепи из одной вершины.

Если немного подумать, то становится ясно, что надо делать так: 1) Все цепи с полуопределённым ребром на одном конце надо замкнуть на себя — для этого надо закинуть в пустую клетку недостающее число. 2) Каждую цепь с полуопределённым ребром на обоих концах надо соединить с цепью без полуопределённых рёбер на концах. При этом образуется цикл. Можно понять, что таких цепей одинаковое количество, а что к чему прицеплять значения не имеет.

Короче это всё очень много мутного текста, но решение на самом деле простое.

Заметим, что Олмек всегда разрушает клетки одного ряда. Это означает, что можно опустошать каждый слой заданного прямоугольника независимо от остальных (в порядке сверху вниз, конечно). Самое главное — научиться опустошать отрезок [L;R) в массиве клеток (т.е. решать задачу при H = 1).

Можно пользоваться такой жадной стратегией опустошения отрезка [L;R). Начинаем в точке x = L. Пока x < R: если клетка [x; x+1) пуста, то перемещаемся из x в x+1 (без затрат) если клетка [x; x+1) полная, то перемещается из x в x+K (потратив одно падение) — т.е. выполняем падение в отрезок [x; x+K] Заметим, что алгоритм строго детерминированный, и проходит по некоторым состояниям x строго по возрастанию.

Рассмотрим граф, в котором вершины — это все состояния x, а рёбра — это описанные выше переходы двух типов. Естественно, все переходы идут строго вправо, и из каждой вершины ровно один переход — то есть это корневое дерево. Весь этот граф можно легко предподсчитать за линейное время. Задача опустошения отрезка [L;R) в терминах графа звучит так: нужно идти из L по переходам, пока не окажешься в R или правее ответом будет количество помеченных переходов на этом пути (т.е. переходов с падением)

Такую задачу можно решать методом двоичного подъёма (примерно как в LCA). Предподсчитаем: A[x,s] = <y,d> для всех 0 <= x <= W и всех 0 <= s <= log W Если выполнить из состояния x ровно 2^s шагов, то мы окажемся в состоянии y, затратив d падений. Имея эту информацию, можно найти бинарным поиском: сколько нужно шагов, чтобы добраться от L до R, и сколько при этом тратится падений.

Затраты: память: O(H * W log W) время : O(H * (W log W + Q log W)) При желании можно сделать O(H * W + W log W) памяти, если прочитать сразу все запросы и решать слои по порядку.

Раз надо сравнивать подстроки, то очевидно нужен суффиксный массив. Прежде всего построим суффиксный массив для S = A#B Имея суффиксный массив, будем работать с суффиксами обеих строк, упорядоченными сверху вниз (условно).

Для начала наивно предположим, что все подстроки различны. Будем перебирать K в порядке убывания от max(M, N) до 1. В каждый момент времени суффиксы длиной меньше K будем называть "мёртвыми", а длиной K или больше — "живыми". Нужно для каждого K узнать количество пар (живой суффикс A, живой суффикс B), таких что суффикс A выше суффикса B.

Можно это количество пар поддерживать и обновлять по ходу уменьшения числа K. Изначально оно равно нулю. На каждом новом K оживает один или два суффикса. Если оживает суффикс A, то надо прибавить к ответу количество живых суффиксов B ниже его. Если оживает суффикс B, то надо прибавить к ответу количество живых суффиксои A выше его. Чтобы быстро определять добавляемое количество, достаточно завести одно или два дерева Фенвика с ноликами/единичками.

Однако если предполагать, что все подстроки различны, то незачем вообще подстроки брать, всё по первой букве определяется; и даже суффиксного массива не надо =) Если же подстроки могут быть одинаковыми, то надо поддерживать дополнительно количество пар суффиксов A/B, у которых первые K символов совпадают. Более того, количество пар на 'меньше' надо периодически уменьшать, т.к. по мере обрезания символов какие-то суффиксы переходят из категории 'меньше' в категорию 'совпадают'.

Чтобы это всё пересчитывать, будем отслеживать множества живых суффиксов, которые совпадают по первым K символами. Каждое такое множество в суффиксном массиве всегда будет отрезком, причём периодически соседние отрезки будут объединяться. Чтобы понять, когда объединения когда происходят, надо посчитать lcp-массив — это lcp между соседними суффиксами в массиве. Для каждого положения, в котором lcp соседей равно K, надо объединить отрезки сверху и снизу от этого положения. В отрезке будет хранить количество суффиксов из A и из B (все суффиксы в отрезке всегда живые).

Итак, в общем случае наши действия на шаге K таковы: 1) Обработать ожившие суффиксы (те, у которых длина равна K): а) для каждого сделать запрос в дерево Фенвика на выше/ниже, добавить полученное количество к ответу б) добавить в дереве Фенвика единичку к позициям оживших суффиксов в) создать для каждого суффикса новый отрезок из одного элемента 2) Объединить соседние отрезки: для каждого места, в котором значение lcp-массива равно K: а) посмотреть на отрезки сверху от него и снизу б) посчитать произведение количества A-суффиксов в верхнем отрезке на количество B-суффиксов в нижнем отрезке (эти пары теперь равны) б) отнять от ответа 'меньше' это произведение, и прибавить его к ответу 'совпадают' в) объединить эти соседние отрезки

Общее время работы: O(N log N)