Wataru

Ваше решение медленно считает сумму на отрезке. За O(n) - вы проходитесь по всему множеству. А все ваше рение будет O(n^2). Когда как это надо делать за O(log n) максимум. Ну посмотрите же на ограничения - n <= 10^5. Обычно n^2 работает ну до 10^4 максимум с огромным скрипом и натяжками.

К сожалению, стандартными set'ами вы сумму на отрезке быстро не подсчитаете. Придется реализовывать сбалансированное бинарное дерево поиска, где в каждой вершине надо дополнительно хранить сумму всех значений в поддереве. Вот реализация дерева, но там сумма на отрезке не реализована. Однако, в статье расказанно, как это делать. Ищите на странице "на отрезке".

Если бы числа в задаче был поменьше, то можно было бы использовать дерево отрезков. Это сильно проще реализуется. Но тут бы это потребовало массивы на 2*10^9 элементов.

Edit: вообще, судя по нескольким вопросам от вас, у вас там задачи именно на реализацию бинарных деревьев поиска с дополнительными данными в вершинах. Вот если у вас следующая задача опять не пройдет по времени, то сначала убедитесь, что вы используете собственноручно написанное дерево поиска.

Все такие вершины являются точками сочленения. Ведь, удалив такую вершину из графа больше не будет пути между двумя вершинами, а значит граф развалился на новые компоненты связности. Есть алгоритм на основе Dfs, который их ищет. Это все работает за O(V+E). Предложенный вами алгоритм с удалением по одной вершине вполне себе работает, но будет медленнее: O(V(V+E)). Для небольших графов может и подойдет.

Потом надо найти путь между заданными вершинами и вывести в ответ точки сочленения. Лучше ищите путь тем же DFSом, что и ищите точки сочленения. Так путь будет идти по дереву DFS. Надо найти в нем LCA двух искомых точек (Пик пути, после которого он пойдет вниз в другую ветку).

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

Не знаю, насколько оптимальное решение это будет давать, но раздувайте прямоугольники по чуть-чуть.

Пусть у прямоугольников будут степени свободы - верх,лево,низ,право. Изначально все прямоугольники раздуваются во все 4 стороны.

Дальше, представьте, что каждый прямоугольник раздувается на 1 пиксель во все стороны за 1 тик.

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

Найдите минимальное время для всех пар. "Отмотайте" это время вперед - раздуйте все прямоугольники на это количество пикселей по всем активным степеням свободы. У двух пересекающихся отберите свободу раздуваться в направлениях, где они коснулись. Если они коснулись по углу, то у вас это будет событие: или они встретились по горизонтали, или по вертикали. Именно эти степени свободы и отбираете.

Повторяйте пока есть хоть одна степень свободы где-то.

Ну и еще надо учитывать пересечения с гарницей поля - точно так же. Считаете время до столкновения.

Может быть так, что пройдет время 0, если куча прямоугольников коснутся в одно и то же время. Это нормально, вы не перематывая время в обработке этого события дезактивируете какие-то степени свободы у каких-то прямоугольников.

Можно просто после каждого столкновения снова искать минимум по всем парам прямоугольников. Можно это соптимизировать знатно через приоритетную очередь, но вряд ли у вас там тысячи прямоугольников и вам это надо делать.

Еще прикол, если прямоугольники пересекутся через пол тика - между ними всего один пиксель. Тут надо будет двигать только один из двух, скажем, с тот у кого номер меньше.

В примере с картинки вы через 0 тиков зафиксируете, допустим, вертикальные границы и потом найдете. что через какое-то время один из прямоугольников упрется в стену. Раздуете оба прямоугольника, зафиксируете упершийся. Дальше, если все симметрично, то второй прямоугольник через 0 тиков тоже упрется в стену.

Правда у этого метода есть проблема Например, вот такая картинка:

AA.B
...B
C...
C.DD

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

В чем проблема перевести с lua на C#?

Там в алгоритме ничего сверх сложного и какой-то встроенной библиотеки не используется. Понятно, что MazeGrid - это двумерный массив? Aux - это класс с методами createGrid (возвращает двумерный массив класса с полями visited, right_wall, bottom_wall), wilson (реализация алгоритма) и всякие вспомогателные hashKey/deHashKey. Еще есть поля width/height/sx/sy.

Сам алгоритм в wilson() использует циклы while и for, if, elseif - все это переводится на C# не задействуя мозг вообще. Чисто механически. Ну, разве что о типах переменных чуть чуть подумать придется. Но, ясно же, что dir - это строка, isMoved - bool.

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

Составьте рекурентное соотношение. Пусть S(k) - сколько шагов надо для вычисления k-ого числа.
Это будет 1 шаг (сумма в конце), плюс сколько надо шагов, чтобы подсчитать слагаемые. Т.е.:
S(k) = S(k-1) + S(k-2) + 1
И известно, что S(1) = S(2) = 0

Уже можно это все подсчитать, как если бы вы числа фиббоначи считали. Хоть рекурсивно, хоть циклом (что, конечно, быстрее).

Но можно добавить в обе стороны урванения +1 и сгрупировать слагаемые аккуратно:
S(k)+1 = S(k-1)+1 + S(k-2)+1

Тогда, если обозначить G(k) = S(k)+1, то получится:
G(k) = G(k-1) + G(k-2) и G(1) = G(2) = 1

Т.е. ответом будет предыдущее число фиббоначи минус один (нам же S(k) = G(k)-1 надо. Плюс, у вас числа с 1,2 начинаются, а тут с 1,1).
Принципиально от вычислений выше не отличается, но наблюдение интересное.

Тут уже предложили всякие питонистые подходы через itertools. Но если их не знать, то подойдет и просто 2 вложенных цикла. Внешний перебирает интервал, а внутренний проходит его значения.