Сделаем двоичный поиск.

Теперь нужно проверить, можно ли взять k человек из двудольного графа, чтобы между взятыми не было ребер. Это независимое множество. Известно, что независимое множество это дополнение вершинного покрытия. Нужно найти максимальное независимое множество -> минимальное вершинное покрытие. Мощность минимального вершинного покрытия в двудольном графе, как известно, равна максимальному паросочетанию.

Нужно еще уметь восстанавливать ответ.

Думаю, тут наиболее понятно будет, хотя у меня зашло и более простое(но не могу доказать, почему верное):
делаем ленивую ДП(Х,У,кто ходит): — при входе ставим что еще считаем ее
— если есть ход в проигрышную позицию, то ответ выигрышная
— если есть ход в ничью, то ответ ничья, при отсутствии хода в выигрышную
— ход в позицию которая еще не до конца обработана = ничейная позиция(то место, которое меня смущает)

там формула выводится. можно заметить что искомая площадь будет площадью n-угольника минус суммарная площадь лишних маленьких треугольников. если сделать рисунок — будет сразу видно. То есть через данный радиус описанной окружности (R = 10 м)найдем сторону n-угольника, а дальше все несложно находится(так как многоугольник правильный) . ну и формула площади треугольника через 2 стороны и и синус угла между ними

В А:
будем перебирать 2 числа 1е и 2е, потом перебирать с конца середину палиндрома и искать перевернутое начало, откинув середину. Аналогично потом делаем с 2м и 3м числом, так-как нужно зафиксить большую часть палиндрома, эти случаи все покрывают, выходит что-то типа О(N*N*Len*Log(N)) с маленькой константой.

В J:
Тут нужно для кажого И — найти А(и) так что-бы отрезок А(И)..И не содержал в себе равных чисел. А дальше будем бин поиском искать отрезки которые нам подходят и лежать полностью, и те которые частично перекрываются с началом и концом: главное что нужно не забыть, что если i A[i]<=A[j].

J: посчитаем массив p[i] — максимальный индекс, такой что на отрезке [i..p[i]] нет повторяющихся, понятно, что при увеличении i p[i] не уменьшается.

посчитать p[i] можно поддерживая левый указатель — i, правый — r и сет отрзезка [i..r], при переходе из i в i+1 удалять из сета a[i]. когда стоим в каком-то i, двигаем r пока можем — пока в отрезке не встречаются повторяющие (проверяем с помощью сета).

построим теперь дерево отрезков для максимума: в ячейке i храним p[i] — i + 1, т.е длину

ответ на запрос [Lq;Rq] делаем так: так как p[i] <= p[i + 1] <= p[i + 2]... найдем бинпоиском такое r, что p[r] <= Rq, а p[r + 1] > Rq на отрезке [Lq, r] найдем максимум.

теперь надо обработать отрезки, которые частично пересекаются, очевидно, что проверять элементы с индексами j (j < Lq), нет смысла, т.к. p[Lq] >= p[j] (опять же), и [Lq..p[Lq]] имеет не меньшее пересечение с отрезком запроса, чем [j..p[j]]. стоит проверить только отрезок [r + 1..p[r + 1]], отрезки [r+2;p[r + 2]], [r+3;p[r+3]]... нет смысла проверять (по той же причине p[r + 1] <= p[r + 2]), отрезок [r + 1..p[r + 1]] будет наибольшее пересечение с запросом