Примеры

Ввод 1 Ввод 2

4 4

0 0 0 1

10 0 1 0

10 10 1 1

0 10 1 0

3 1

0 1 1 0 0 0 1 1

9 11 11 9

9 -1 100 100

Вывод 1 Вывод 2

1 1

1 1

2 1

0 1

15.2. Разноска пиццы (15)

В городе X все улицы параллельны координатным осям. Каждая точка с целочисленными координатами является пересечением двух улиц. Кварталы плотно застроены небоскребами, поэтому расстояние между точками (X₁, Y₁) и (X₂, Y₂) определяется как | X₁ - X₂ | + | Y₁ - Y₂ |. Компания по разноске пиццы имеет в городе N точек. Покупателям пицца приносится мальчиками, которые передвигаются с разной скоростью, поэтому для каждой пиццерии известно максимальное расстояние, на которое может быть доставлен заказ. Кризис вынуждает закрыть ряд пиццерий. Было принято решение закрыть какие-либо пиццерии из тех, которые находятся в пределах досягаемости не менее чем из K других пиццерий. Требуется выявить все пиццерии, которые могут оказаться зарытыми.

Ввод из файла INPUT.TXT. В первой строке находятся два целых числа N и K через пробел (2   N  10⁵, 1   M  N -1). Следующие N строка содержат целочисленные координаты очередной пиццерии X, Y и максимальное расстояние W для доставки пиццы (0   X, Y, W   10⁹ ).

Вывод в файл OUTPUT.TXT. В первой строке выводится число пиццерий T, которые могут быть закрыты. Вторая строка содержит T целых чисел через пробел – номера пиццерий, которые могут быть закрыты в порядке возрастания их номеров.

Примеры

Ввод 1 Ввод 2 Ввод 3

2 1 3 2 3 2

0 0 1 0 0 1 0 0 100

1 0 1 13 17 5

10 3 1 10 10 10

Вывод 1 Вывод 2 Вывод 3

2 0 1

1 2 2

Подсказка

Геометрическим местом точек, удаленным не более чем на W от точки (X, Y), будет квадрат с вершинами в точках (X - W, Y), (X + W, Y), (X, Y- W), (X, Y+ W). Чтобы стороны квадратов стали параллельными осям координат, выполним поворот всех точек на π/4 относительно начала координат против часовой стрелки. Тогда координатами новых точек будут

X' = (X√2 - Y√2)/2 ; Y' = (X√2 + Y√2)/2 . _

Далее выполним масштабирование координат с коэффициентом √2. Новые координаты примут простой вид

X' = X - Y ; Y' = X + Y .

После преобразования длина стороны квадрата станет равной 2W, то есть преобразование сохраняет целочисленные значения координат точек и дает целочисленное значение стороны квадрата. Далее нужно применить метод сканирующей прямой и с помощью дерева отрезков с функцией суммы обработать стандартные события.

15.3. Построение (9)

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

Ввод из файла INPUT.TXT. Первая строка содержит количество команд N (1   N  30000). В каждой следующей строке содержится описание команды: числа 1 и X, если солдат приходит в строй (X – рост солдата от 1 до 100000) и числа 2 и Y, если солдата, стоящего в строю на месте Y надо удалить из строя. Солдаты в строю нумеруются с 1.

Вывод в файл OUTPUT.TXT. На каждую команду 1 (добавление в строй) нужно выводить в отдельной строке число K – номер позиции, на которую должен встать этот солдат (все стоящие за ним двигаются назад).

Пример

Ввод

5

1 100

1 200

1 50

2 1

1 150

Вывод

1

1

3

2

15.4. Сугробы на ЛЭП (9)

Служба электроснабжения проводит мониторинг уровня снега, лежащего на ЛЭП. Вся ЛЭП разбивается на участки опорами. Если снег падает на некоторый интервал ЛЭП, то высота снежного покрова на этом интервале увеличивается на высоту выпавшего снега. Снег также имеет тенденцию таять на некотором участке трассы в результате оттепели, однако сугробов отрицательной толщины быть нет может. Энергетикам крайне важно уметь узнавать суммарную высоту снежного покрова на некоторых участках, чтобы определять вероятность обрыва проводов.

Ввод из файла INPUT.TXT. В первой строке находятся через пробел два числа: N – количество опор (1   N  10000) и M – количество команд (1   M  50000). Команды бывают двух видов:

• 1 L R S - на участок с L-й опоры по R-ю выпало S сантиметров снега;

• 2 L R – запрос о высоте снега на участке от L-й опоры по R-ю.

Таяние снега показывает первый вид команды с отрицательным значением S. Опоры нумеруются от 1 до N.

Вывод в файл OUTPUT.TXT. На каждый запрос (команду второго вида) требуется выводить суммарную высоту снежного покрова, лежащего на проводах от L-й опоры по R-ю.

Пример

Ввод

11 5

1 1 10 10

1 2 6 -3

2 5 9

1 1 7 25

2 1 3

Вывод

37

67

15.5. Оранжерея (15)

Оранжерея представляет собой прямоугольный участок для выращивания растений пермского периода. Оранжерея была разбита дорожками на квадраты. В центре каждого квадрата посажено одно растение. Размер квадрата зависит от корневой системы растения.

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

Введем декартову прямоугольную систему координат, начало которой совмещено с левым нижним углом оранжереи. Ось Ox направлена вдоль нижней границы участка, ось Oy – вдоль левой. Изначально дорожки были проложены параллельно осям координат. Единичный отрезок удалось выбрать так, что координаты углов каждого из квадратов оказались целыми.

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

Ввод из файла INPUT.TXT. В первой строке записаны три натуральных числа: W – ширина оранжереи, H – длина оранжереи и N – количество посаженых растений (N ≤ 2×10⁵). В каждой из следующих N строк расположены по два числа: x_i, y_i – координаты i-го растения (0 < x_i < W, 0 < y_i < H, x_i, y_i ≤ 2×10⁹). Гарантируется, что соответствующие растениям квадраты имеют целую длину стороны и покрывают всю оранжерею.

Вывод в файл OUTPUT.TXT. Необходимо вывести N целых чисел – размеры квадратов, соответствующих растениям. Числа вывести в порядке описания растений во входном файле.

Примеры

Ввод 1 Ввод 2

4 6 3 8 8 10

1 1 4.5 7.5

3 1 5.5 7.5

2 4 2 6

4.5 6.5

7 7

5 5

6 2

7 5

2 2

5.5 6.5

Вывод 1 Вывод 2

2 1

2 1

4 4

1

2

2

4

2

4

1

Примечание. Оранжерея во втором примере соответствует следующему рисунку:

16. Дерево Фенвика

Из предыдущего раздела видно, что дерево отрезков программируется достаточно сложно. Еще больших сложностей требует реализация без применения рекурсии. Затраты памяти хотя и пропорциональны величине N, но коэффициент пропорциональности k = 4 даже в простейшем случае.

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

Пусть задан массив A из N чисел: A₀, A₁, . . . , A_N-1. C помощью дерева Фенвика можно выполнять две операции:

• Rsq(I, J) – нахождение суммы элементов массива A в диапазоне индексов от I-го до J-го;

• Update(K, D) – изменение K-го элемента массива A на величину D.

В отличие от дерева отрезков не обеспечивается операция Rmq – нахождение максимума элементов массива в заданном диапазоне индексов и операция интервальной модификации элементов.

Как уже говорилось выше, при простейшей работе с массивом A запрос Rsq(I, J) работает за время O(j − i + 1), что в общем случае составляет порядок O(N), а Update(K, D) - за O(1). C помощью дерева Фенвика каждая из указанных операций выполняется за время O(logN).

На практике дерево Фенвика представляет собой массив B из N чисел: B₀, B₁,…, B_{N -1}, в k-м элементе которого хранится сумма элементов массива A с f(k)-го по k-й:

,

где f(k) = k &(k + 1). Под ”&” имеется в виду операция побитового И (AND).

Рассмотрим двоичную запись числа k и посмотрим на его младший бит. Если он равен нулю, то f(k) = k. Иначе число k оканчивается группой из одной или нескольких единиц. Заменим все эти единицы на нули и присвоим полученное число значению f(k).

Следующий рисунок показывает, что хранится в массиве B. Клетка i - ой строки и k - го столбца черная, если A_i входит в частичную сумму B_k, то есть f(k) ≤ i ≤ k.

Из рисунка видно, например, что A₂ входит в качестве слагаемого в B₂, B₃ и B₇.

Рассмотрим, как с помощью дерева Фенвика реализуются операции ответа на запрос Rsq(i, j) о частичной сумме элементов массива A с i-го по j-й.

Заметим, что Rsq(i, j) = Rsq(0, j) − Rsq(0, i − 1). Для i = 0 положим Rsq(0,−1) = 0. Таким образом, для ответа на запрос Rsq(i, j) достаточно научиться отвечать на запрос вида Rsq(0, k), который для краткости обозначим Rsq(k).

Вместо того, чтобы проходить по всем элементам массива A, будем двигаться по массиву B, совершая прыжки через отрезки там, где это возможно. Поскольку

B_k = A_f(k) + A_{f(k) + 1} + … + A_k,

то

Rsq (k) = (A₀ + A₁ + … + A_{f(k) – 1}) + (A_f(k) + A_{f(k) + 1} + … + A_k) =

= Rsq (f(k) – 1) + B _k = Rsq(f(f(k) – 1) – 1) + B_{f(k) – 1} + B_k = …

Указанная сумма расписывается до тех пор, пока значение f(…(f(f(k) – 1) – 1) …) не станет равным нулю. То есть Rsq(k) состоит из сумм элементов массива A на отрезках [f(k); k], [f(f(k) – 1); f(k) – 1] и так далее.

Рассмотрим, например, процесс вычисления Rsq(14):

ki	f(ki)	ki+1 = f(ki) – 1
14 = 11102	11102 = 14	13
13 = 11012	11002 = 12	11
11 = 10112	10002 = 8	7
7 = 1112	0002 = 0	стоп

Из таблицы следует, что Rsq(14) = B₁₄ + B₁₃ + B₁₁ + B₇. Или то же самое, что суммируются интервалы: Rsq(14) = A[14..14] + A[12..13] + A[8..11] + A[0..7].

Ниже приводится текст функции, реализующий ответ на запрос Rsq(k).

Function Rsq(k: LongInt): LongInt;

Var

res : LongInt;

Begin

res:=0;

While (k >= 0) do

begin

inc(res, B[k]);

k := k and (k + 1) - 1;

end;

Rsq:=res;

End;

Для оценки времени работы данной функции необходимо оценить количество итераций цикла While в строках, то есть количество слагаемых в итоговой сумме. Количество слагаемых на единицу больше количества единичных битов в числе f(k). Переход к каждому следующему индексу ”выбивает” ровно по одному единичному биту из числа f(k_i). А поскольку в худшем случае количество единичных бит в f(k) может быть порядка O(logN), то и ответ на запрос Rsq(k) в худшем случае требует порядка O(logN) времени.

При изменении k-го элемента массива A необходимо соответствующим образом изменить элементы массива B, в определении которых частичные суммы содержат элемент A_k. То есть для выполнения операции Update(K, D) нужно прибавить D к тем элементам B_i, для которых f(i) ≤ k ≤ i.

Рассмотрим, как имея число k, быстро находить такие числа i, что f(i) ≤ k ≤ i. Оказывается, что все такие числа i получаются из k последовательными заменами самого правого (младшего) нуля в двоичном представлении.

Пусть, например, k = 8 = 1000₂. Последовательно заменяя последний 0 в двоичном представлении k на 1, получим числа: 1001₂ = 9, 1011₂ = 11, 1111₂ = 15, 11111₂ = 31, 111111₂ = 63 и т. д. Следовательно A₈ будет содержаться в B₈, B₉, B₁₁, B₁₅, B₃₁ B₆₃ и т. д.

Пусть k = 53 = 110101₂. Аналогично заменяя последовательно по одному последнему нулю, получим числа: 110111₂ = 55, 111111₂ = 63, 1111111₂ = 127 и т. д. Следовательно, A₅₃ содержится в B₅₃, B₅₅, B₆₃, B₁₂₇ и т. д.

Введем функцию H(k) = k | (k + 1), которая заменяет последний нуль в двоичном представлении числа k на единицу. Под "|” имеется в виду операция побитового ИЛИ. Для выполнения операции Update(K, D) необходимо прибавить D к элементам массива B с индексами k₀, k₁, …, k_p , где k₀ = k, k_j+1 = H(k_j) = k_j | (k_j + 1). Цикл добавления D завершается как только k_p+1 станет большим N.

Ниже приводится текст процедуры, реализующий операцию Update(K, D).

Procedure Update(k,d: LongInt);

Begin

While (k < N) do

begin

inc(B[k],D);

k := k or (k + 1);

end;

End;

В силу того, что длина последовательности k_i составляет O(logN) в худшем случае, количество итераций цикла While, а значит и время работы процедуры составляет O(logN).

Для построения дерева Фенвика по заданному массиву A достаточно обнулить массив B и N раз выполнить операцию изменения элементов: Update(0, A₀), Update(1, A₁), …, Update(N−