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

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, а вдруг более длинная последовательность, найденная НВП даст невкладывающиеся прямоугольники? Вам надо в обе стороны доказать соответствие последлвательности в массиве и последоватеньности матрешки.

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

Как "склеить" два файла?

Неясно, что конкретно вам надо. Почему нельзя просто перезаписать hello-world файлом evil-hello-wolrd? Что значит "склеить"? Вам надо, чтобы итоговый файл какую программу выполнял? Вам надо какие-то дополнительные условия, вроде неизменения размера файла? Или возможность откатить его назад к hello-world?

Как решать задачи на разбиение фигуры на сектора по цветам?

Каждый сектор должен быть равен сектору +i. Если идти по секторам с шагом +i, то рано или подзно мы вернемся туда, откуда начали - это и есть цикл.

Его длина (в секторах) делится на i, потому что мы по i секторов скачем. И к тому же она делится на 42, ведь мы прошли сколько-то полных кругов, чтобы вернуться в начало. Итого, эта длина НОК(i, 42). Но это длина в секторах, считая пропущенные i-1. Всего цикл посетит НОК(i, 42)/i секторов. А, поскольку все циклы одинаковые, то их всего 42/длина-цикла-в-посещенных-секторах, т.е. 42*i/НОК(i,42). И это получится GCD(i, 42).

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

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

Почему отказались от оператора GoTo в высокоуровневых языках?

Ланской Кирилл,

Почему в новых языках программирования goto нет?

По той же причине, почему во многих кодовых базах на Си запрещают goto использовать. Я об этом в ответе же написал - с goto можно легко написать очень непонятный код.

Почему отказались от оператора GoTo в высокоуровневых языках?

Что есть какой-нить JC label как не IF (carry_flag IS SET) {GOTO label} ELSE {}?

Это условный переход. Разница с if/else в том, что тут в ветке If гвоздями прибит goto. Это в первую очередь переход, а уже потом условие.

Как решить задачу по Token Ring?

Вы или скопировали или поняли условие криво. Передача от компьютера 1 кому передается? В token ring за сумму всех времен токен пройдет по кругу. При этом токен будет переносить сообщение с первого компьютера, пока оно не дойдет до получателя. Потом пустой токен дойдет до первого компьютера и тот передаст его дальше по кругу. Тут уже другие комьпютеры могут начать передачу данных. Когда токен дойдет назад до первого компьютера он сожет отправить следующее сообщение.

Так что надо знать кто получатель и сколько фреймов занимают отправляемые данные.

Как вывести минимальный элемент из динамической библиотеки?

jidomasson, Ну тогда передавайте A и size. так же как и в arrRandom

Как вывести минимальный элемент из динамической библиотеки?

jidomasson, а как вы эту функцию вызываете-то? И давайте код arrRandom.

Я бы функцию min_element переписал - вместо рекурсии просто бы циклом while прошелся. И вообще бы поменял у нее аргументы на те же, что и у arrRandom - указатель и размер.

Как правильно сдвинуть биты?

A = 0 a7 1 b6 c5 a3 b2 c1

Непонятно, что эта запись обозначает. a,b,c - это входные биты? У вас входнгея группа из трех символов - там 24 бита. Какие 6 из них нужно взять?

Или вы имеете ввиду a7 - это 7ой (считая с 0) бит первого символа. c1 - 1ый (считая с 0) бит третьего символа?

Что подразумевается под поиском двух линий при создании контейнера?

MishaXXL, Потому что вам надо максимизировать min(h[i],h[j])*(j-i). Вот в currentArea вы и берете этот min из двух столбцов. А в maxArea берете максимум из значений, которые и надо максимизировать.

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

U235U235, нет, тут надо получить один многоугольник, а в триангуляции вы получите кучу треугольников.

Как исправить ошибку undefined reference to при коспиляции кода с++ в VS?

sharkee, Нет. В cmake файле надо указать оба cpp файла.