Какой правильный класс коллекции для хранения сортируемого списка?

Более тооо, я предлагал еще по id объектов хранить итератор в списке, чтобы не надо было обходить весь список для поиска объекта. Ну и, я не специалист по жаве, но думаю, что там тоже из дека нельзя удалять элементы из центра. Нужен именно list.

Как записать это выражение?

historydev, Почему при письме читается слева-на-право? Ну нет особой причины, просто в нашем языке так принято. Вон, в арабском, наоборот - справа-на-лево читается. Так же и числа. Просто в системе с арабскими цифрами как-то так сложилось, что младшие разряды - справа. Никакой особой причины тут нет. Могло бы быть и наоборот.

Как записать это выражение?

historydev, Ну, так принято. Вон в десятичной системе же справа единицы, а миллиарды - совсем слева. Также и в двоичной. Слева- единицы, потом двойки (вместо десяток), потом четверки (вместо сотен) и т.д.

Как записать это выражение?

historydev, Иногда и без скобочек пишут, когда из контекста понятно

Как записать это выражение?

historydev, нижний индекс у скобочек - это стандартное обозначение системы счисления.

Как записать это выражение?

historydev, "Основание системы счисления". Для двоичной системы - это 2. Для десятичной - 10.

Почему паралельная сортировка слиянием выполняется на cpu быстрее чем на gpu в 100 раз?

Данные-то проверяли, оно сортирует вообще? Не тормозит ли загрузка и выгрузка данных с GPU?

Почему появляется лишний символ при открытии файла qt C++?

А, проблема в 6. Откройте файл в Hex редакторе, что там в начале-то? Потому что, если вы его блокнотом открваете, а это какой-то странный символ, вы его не увидите. Скорее всего проблема с файлом из-за "передачи по сокетам".

Почему появляется лишний символ при открытии файла qt C++?

Если этот файл открыть в каком-нибудь hex редакторе, нет ли там в начале этих же нулевых байтов?

Что не так в решении задачи?

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

Что не так в решении задачи?

Алексей Уколов, Ну, если стоит задача вывести какой-то мусор, то - да, массив не нужен.

Что не так в решении задачи?

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

Как найти решение для задачи?

Rsa97,

То есть, добавляя, например, интервал (1, 6) мы всё равно будем добираться до всех листьев в этом интервале?

Нет. Мы же останавливаемся, когда текущая вершина покрыта целиком обновляемым отрезком. Не надо спускаться до листьев. В итоге спустимся до O(log n) вершин. Так, 1..6 разбивается на 1..3 и 4..6. 1..3 - на 1..1 и 2..3, а 4..6 - на 4..5 и 6..6.

Так же и при поиске минимума: рекурсинво спускаемся, пока текущая вершина не станет целиком лежать в искомом отрезке.

Мы обойдем максимум 4log n вершин, это можно доказать. После первого же деления пополам, потому что искомый отрезок есть и слева и справа, будет ситуация, что искомый отрезок касается отрезка-вершины с одного конца. В этом случае второе деление пополам сразу завершит одну из веток.

Как найти решение для задачи?

Rsa97, Не надо ничего разбивать. Дерево отрезков работает над массивом в 2n элементов. Пусть тут будет от 0 до 7. Корень отвечает на все 8 элементов, 2 ребенка - за 2 половинки: 0..3 и 4..7. И т.д. до листьев, которые отвечают за один элемент. Каждая вершина хранит минимум из двух детей. Обычно их хранят в массиве так что у вершины i дети 2*i+1 и 2*i+2.

Для отрезков [(0, 4), (1, 3) (2, 5)] вы получите массив вида

[0,    1, 0,    1, 2, 0, 0,   1, 2, 3, 2, 1, 0, 0, 0]

. Последние 8 элементов изменены за счет +1 от всех трех отрезков и хранят, сколько отрезков покрывает [i..i+1]. Предыдущие 7 элементов хранят минимум. Так что видно, что в корне 0, а значит на всем отрезке 0..8 есть пустые места. Но чуть дальше стоит 1, а значит отрезок 0..4 покрыт хотябы по одному разу.

Добавление на отрезке делается чуть сложнее, через отложенное добавление - надо хранить второй массив, сколько на всем текущем отрезке надо добавлять, и при выполнении операции идти рекурсивно от корня к листьям, пока нельзя весь текущий отрезок увеличить на 1, тогда эта 1 добавляется во второй массив. А при поиске минимума (тоже рекурсивно) надо перед любым обращением к вершине сначала спустить отложенное добавление в двух ее детей.

Работает за O(log n) и добавление на отрезке и проверка минимума на отрезке.

Как найти решение для задачи?

Alexandroppolus, Нет, тут проблема в самом начале, например. Дерево пустое. Открыли вы один прямоугольник, в дереве куча нулей. Но они закроются другими прямоугольниками в этот же момент времени.

Ошибка в коде с++?

Вижу одну ошибку - n и n1 в циклах перепутаны. Это потому что надо использовать нормальные имена переменных - вроде kHeight и kWidth.

Что касается вопроса - вы ошибку компилятора прям сюда копируйте. А среде разработки может из-за неправильных границ что-то не нравится.

Этот код должен компилироваться без проблем.

Еще, оберните код в тег code (кнопка </> в редакторе). А то влпрос удалят за нарушение правил.

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

historydev, лексикографически - в смысле сначала минимизируем i, а среди всех минимальных минимизируем j.

Можете описать, что эти отрезки-то значат? Что это за очередь?

Т.е. ищем пару i < j, т.ч. один из них входит в другой, с минимальным i, из всех таких - с минимальным j?

Вам надо будет потом эту пару из очереди удалять и опять искать пару? Что вы потом с этой парой делаете? От этого зависит, какой алгоритм самый лучший.

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

Не ясна задача. Сравниваются-то пары отрезков. Что значит в порядке "первый пришел первый ушел"? Это порядок на один отрезок. Вот у вас N отрезков. Надо найти такие i и j, что отрезок i входит в отрезок j. Но какие условия на i, j? Лексикографически минимальная пара?

Что значит "входит"? Входит ли отрезок [18, 18] в [10, 18]? Совпадающие отрезки считаются за вхождение?

Можно ли так доказывать правильность алгоритмов?

floppa322, да это частый подход. Рассматриваем оптимальный ответ и что-то про него доказываем

Можно ли так доказывать правильность алгоритмов?

floppa322, а вдруг более длинная последовательность, найденная НВП даст невкладывающиеся прямоугольники? Вам надо в обе стороны доказать соответствие последлвательности в массиве и последоватеньности матрешки.

Перевооачивать, да, но это же отдельный прием для борьбы с этим.