Вам надо удалить прямоугольник с экрана? Есть два метода - перерисовывайте весь экран каждый раз. В следующем кадре прямоугольника уже не будет, вы же не будете передавать в draw удаленный прямоугольик. Или, если он ни с чем не пересекается, его можно перед удалением закрасить светом фона.
Это если вам надо подсчитать только количество отрезков в одной конкретной точке. В вопросе в примере выводятся количества для всех клеток сразу. В этом случае ваш метод далеко не самый оптимальный. И еще, в каком языке есть такие двойные сравнения? Придется писать left<=x && x<=right
dollar, Обобщение это задачи (подсчитать сколько клеток покрыто отрезками на прямой) - это прямоугольники на плоскости. И там точно такой же трюк есть: в 4 угла поставить +1 и -1 (по диаганали знаки, правые/верхние сдвинуты на 1 наружу). Потом делаем 2 прохода по плоскости - сначала по строкам, потом по столбцам: и также накапливаем частичные суммы.
Если плоскость большая и надо, допустим, самую плотно покрытую точку найти - то можно двумерное дерево отрезков запилить. Или для экономии памяти - мою любимую структуру данных: дерево отрезков декартовых деревьев (в бинарном дереве точно также можно делать добавление на отрезке, как и в дереве отрезков).
Если же брать другое обобщение этой задачи - именно отрезки на плоскости, то там уже общих пересечений особо может и не быть вообще. Ибо два отрезка на плоскости пересекаются по точке. Что вы там хотите найти - все точки пересечения?
Но в таких задачах все-равно часто работает метод сканирующей прямой (решение, что я привел к вопросу - по сути и есть частный случай этого метода). Там можно, например, найти есть ли пересечение среди N отрезков за N log N.
Сергей Соколов, Почему? +1 ставится в позицию 1, -1 в позицию 2 (я же написал "в координату за правым концом").
При проходе сделаем +1 в позиции 1 и выведем 1. Потом в позиции 2 вычтем 1 и получим правильный 0.
Edit, слегка подправил формулировку в ответе, чтобы понятнее было.
Alexandroppolus, Вообще, есть идея не хранить сами числа, а хранить только степени 2, 3 и 5 и вычислять большое число только в самом конце. Но тогда надо уметь 100% точно сравнивать 2 числа в таком виде. Если сравнивать ln2*i+ln3*j+ln5*k, то у дабла должно вполне хватить точности на много дольше, чем если бы в int64_t числа считать.
Alexandroppolus, Это не так важно, потому что эти самые числа растут експоненциально (если до N их O((lnN)^3) - значит K-ое число порядка O(e^(k^(1/3))). Поэтому гораздо раньше придется беспокоится об длинной арифметике и размере самих чисел, преже чем о их количестве.
Теперь про размер списка. Ваш анализ не совсем точен. N - это само послледнее число. ln N - его длина. Растет оно примерно как количество чисел ^1/3. Таким образом, если вы генерируете первые K чисел, вам надо O(k^2/3) чисел. Не слишком большая экономия.
Ну вот 2, 3, 4, 5, 6, 8, 9, 12, 15 - это числа хемминга, потому что они являются произведением сколько-то двоек, троек и пятерок. 7, 14 и 23 - не являются, потому что в разложении на простые множители содержат еще что-то кроме 2, 3 и 5.
Rsa97, Опишите свой алгоритм на бумажке и попробуйте подсчитать, сколько там операций. Все те же самые O(L^2) вы и получите. Тот логарифм, который вы сюда впихиваете - он от числа X - и будет как раз длиной L.
Не зря умные дядьки 60 лет голову ломают над алгоритмами быстрого умножения длинных чисел.
red_crocodile, массив - указать и длина. Вам можно длину прередавать везде вместе с массивами. Создается массив через malloc (или new, если у вас, таки, C++)
ThunderCat,
Ваша логика вообще не работает. Например, сумма обратных для всех чисел, не содержащих цифру 7 в записи - сходится. А таких, кажется, нисколько не меньше, чем простых чисел. А сумма обратных простым - расходится.
longclaps, Какая разница, что за пространство. Главное, что в нем метрика есть - количество шагов. Осталось только эвристику подобрать. Это может быть не тривиально, но, например, если все действия меняют ровно одно поле в зависимости от каких-то условий, то может быть эвристика - сколько полей не совпало с конечным состоянием. Эта эвристика допустима - она не переоценивает никакой путь. Она еще и консистентна. Отлично подходит для A*.
