16. Дерево отрезков
Дерево отрезков - структура данных, которая позволяет реализовать с трудоемкостью O(log N) операции следующего типа:
- Add(I, J, D) – изменение на величину D элементов массива в диапазоне индексов от I-го до J-го; Update (I, J, V) – присвоение элементам массива в диапазоне индексов от I-го до J-го нового значения V; Rsq(I, J) – нахождение суммы (Rmq – максимума) элементов массива в диапазоне индексов от I-го до J-го.
Обычно обеспечиваются совместно первая и третья либо вторая и третья функции. Объём дополнительно используемой памяти составляет O(N), или, если быть точным, не более 8N на каждую пару функций.
Распространенная аббревиатура Rsq расшифровывается как Range Sum Query, а Rmq как Range Maximum Query.
Обычный массив позволяет выполнить с минимальной трудоемкостью O(1) операцию изменения одного элемента, но указанные операции имеют трудоемкость O(N). Если они должны выполняться часто, то при большой размерности массива это оказывается недопустимым.
Рассмотрим сначала дерево отрезков для суммы. Пусть имеется массив A[1], A[2],…, A[N]. Построим бинарное дерево T следующим образом. Корень дерева будет храниться в элементе T[1] и содержать сумму элементов всего массива. Левый сын корня будет храниться в элементе T[2] и содержать сумму первой половины массива: A[1..N div 2], а правый сын - в элементе T[3] и содержать сумму элементов A[N div 2+1..N]. В общем случае, если i-й элемент содержит сумму элементов с L-го по R-й, то его левым сыном будет элемент T[2*i] с суммой элементов A[L..(L+R) div 2], а правым – элемент T[2*i +1] с суммой A[(L+R) div 2+1..R]. Исключение, разумеется, составляют листья дерева - вершины, в которых L = R. Дерево состоит из 2N-1 вершин, строится с трудоемкостью O(N) и имеет высоту порядка O(log N).
Рассмотрим теперь операцию суммы на некотором отрезке индексов [L; R]. Мы встаем в корень дерева (i=1), и рекурсивно движемся вниз по этому дереву. Если в какой-то момент оказывается, что L и R совпадают с границами отрезка текущего элемента, то мы просто возвращаем значение текущего элемента T. Если же отрезок [L; R] целиком попадает в отрезок левого или правого сына текущего элемента, то мы рекурсивно вызываем себя из этого сына и найденное значение возвращаем. Наконец, если отрезок [L; R] частично принадлежит и отрезку левого сына, и отрезку правого сына, то делим его на два отрезка [L; M] и [M+1; R], где M = (L+R) div 2, и рекурсивно вызываем себя и для первого, и для второго отрезков, возвращая сумму найденных значений. В итоге вся операция суммирования работает за O (log N).
Теперь рассмотрим простейший вариант операции присвоения значения некоторому единственному элементу с индексом K. Будем спускаться по дереву от корня, ища тот лист, который содержит значение элемента A[K]. Когда мы найдём этот элемент, просто изменим соответствующее значение в массиве T и будем подниматься от текущего элемента обратно к корню, пересчитывая текущие значения T. Понятно, что таким образом мы изменим все значения в дереве, которые необходимо изменить. Общая трудоемкость составляет O(log N). Приведем реализацию описанных операций.
Procedure Build(i, L,R: longint);
{Построение дерева отрезков для суммы
i - номер вершины, L - нижняя граница в исходном массиве,
R - верхняя граница, первоначально 1 и N}
Var
m: longint;
Begin
if L=R then T[i]:=A[L]
else
begin
m:=(L+R) div 2;
Build(2*i, L,m);
Build(2*i+1,m+1,R);
T[i]:=T[2*i]+T[2*i+1];
end;
End;
Function Sum(L, R,i, Tl, Tr:longint):longint;
{L, R - интервал индексов в A для суммы - первоначально 1 и N,
Tl, Tr - границы поиска в массиве A, - первоначально 1 и N}
Var
m: longint;
Begin
if (L=Tl) and (R=Tr) then Sum:=T[i]
else
begin
m:=(Tl+Tr) div 2;
if R<=m then Sum:=Sum(L, R,2*i, Tl, m)
else
if L>m then Sum:=Sum(L, R,2*i+1,m+1,Tr)
else
Sum:=Sum(L, m,2*i, Tl, m)+Sum(m+1,R,2*i+1,m+1,Tr);
end;
End;
Procedure Update(Ind, NewVal, i,L, R:longint);
{одиночная модификация: в A[Ind] новое значение NewVal}
Var
m: longint;
Begin
if L=R then T[i]:=NewVal
else
begin
m:=(L+R) div 2;
if Ind<=m then Update(Ind, NewVal,2*i, L,m)
else Update(Ind, NewVal,2*i+1,m+1,R);
T[i]:=T[2*i]+T[2*i+1];
{пересчет значений при возврате из рекурсии}
end;
End;
Операция прибавления на отрезке реализуется сложнее одиночной модификации. Введем дополнительный массив Add размерности 2N – 1 и той же адресации, что и массив T. В i-м элементе будем хранить Add[i] - значение, которое нужно прибавить ко всем элементам этого отрезка. Если добавка распространяется не на все элементы, то это будет отражено в соответствующих вершинах поддерева с корнем I. Операция прибавления на отрезке [L; R] будет модифицировать эти значения, а операция суммирования на отрезке - просто добавлять к ответу все встретившиеся значения Add на пути от корня до вершин, которые представляют в совокупности отрезок [L; R].
Рекурсивная процедура Plus прибавления на отрезке имеет аргументы L, R, X, I, Tl, Tr. Здесь L и R описывают диапазон индексов исходного массива A, на котором к каждому элементу прибавляется значение X. Параметр I определяет индекс вершины в дереве T, содержащей диапазон индексов [Tl; Tr] исходного массива для поиска всех вершин дерева, которые описывают совместно отрезок [L; R]. Первоначально I = 1, что соответствует корню дерева. Значения Tl = 1 и Tr = N задают полный диапазон индексов исходного массива A. Значение X может быть как положительным, так и отрицательным. Порядок рекурсивных вызовов принципиально не меняется, что видно из текста процедуры Plus.
Procedure Plus(L, R,X, i,Tl, Tr:longint);
{в интервале индексов [L, R] к элементам A добавляется X}
Var
m: longint;
Begin
T[i]:=T[i]+X*(R-L+1);
if (L=Tl) and (R=Tr) then Add[i]:=Add[i]+X
else
begin
m:=(Tl+Tr) div 2;
if R<=m then Plus(L, R,X,2*i, Tl, m)
else
if L>m then Plus(L, R,X,2*i+1,m+1,Tr)
else
begin
Plus(L, m,X,2*i, Tl, m);
Plus(m+1,R, X,2*i+1,m+1,Tr);
end;
end;
End;
Рекурсивная функция суммирования имеет те же аргументы и строится по тому же принципу. Поскольку массив Add описывает изменение каждого элемента в диапазоне индексов [L; R], то общая добавка составляет сумму Add[i]*(R-L+1) по всем путям от корня дерева к вершинам, представляющим совместно весь диапазон [L; R].
Function Sum(L, R,i, Tl, Tr:longint):longint;
{L, R - интервал индексов для суммы,
Tl, Tr - границы поиска в дереве}
Var
m, h: longint;
Begin
if (L=Tl) and (R=Tr) then Sum:=T[i]
else
begin
m:=(Tl+Tr) div 2;
h:=Add[i]*(R-L+1);
if R<=m then Sum:=Sum(L, R,2*i, Tl, m)+h
else
if L>m then Sum:=Sum(L, R,2*i+1,m+1,Tr)+h
else
Sum:=Sum(L, m,2*i, Tl, m)+Sum(m+1,R,2*i+1,m+1,Tr)+h;
end;
End;
Трудоемкость обеих рассмотренных операций по-прежнему составляет O(log N).
Операция присвоения нового значения на диапазоне индексов реализуется с помощью дополнительного массива Val размерности 2N – 1 и той же адресации, что и массив T. Изначально массив Val заполняется некоторыми значениями, имеющими смысл ”неопределенность”. Если все элементы в текущем отрезке индексов массива T равны между собой, то соответствующий элемент массива Val примет это значение. При выполнении операции присвоения мы будем спускаться по дереву, как и ранее. Если в какой-то момент диапазон присваивания совпадет с границами текущего отрезка, то мы присвоим соответствующему элементу Val новое значение. При спуске необходимо отменять ранее определенные значения Val.
Операция суммирования тоже должна быть изменена. Если при спуске в какой-то момент встречается элемент Val, отличный от неопределенного, то спуск прекращается. Действительно, результат уже определен значением элемента Val. При продолжении спуска были бы получены неправильные, старые значения.
Приведем тексты программ для реализации описанных операций.
Procedure Update(L, R,NewVal, i,Tl, Tr:longint);
{в интервале индексов [L, R] в A[i] новое значение NewVal,
i-корень дерева отрезков}
Var
k, m: longint;
Begin
if (L=Tl) and (R=Tr) then
begin
Val[i]:=NewVal;
T[i]:=NewVal;
end
else
begin
k:=Val[i];
Val[i]:=-1;
if k<>-1 then
begin
Val[2*i]:=k; {спуск на уровень}
Val[2*i+1]:=k;
end;
m:=(Tl+Tr) div 2;
if R<=m then Update(L, R,NewVal,2*i, Tl, m)
else
if L>m then Update(L, R,NewVal,2*i+1,m+1,Tr)
else
begin
Update(L, m,NewVal,2*i, Tl, m);
Update(m+1,R, NewVal,2*i+1,m+1,Tr);
end;
T[i]:=T[2*i]+T[2*i+1];
{пересчет на обратном пути при выходе из рекурсии}
end;
End;
Function Sum(L, R,i, Tl, Tr:longint):longint;
{L, R - интервал индексов для суммы, i-корень дерева,
Tl, Tr - границы поиска в дереве}
Var
m: longint;
Begin
if (Val[i]<>-1) then Sum:=Val[i]*(R-L+1)
{все вершины дерева с корнем i имеют значение Val[i]}
else
if Tl=Tr then Sum:=T[i]
{дошли до листа без модификации значений}
else
begin
m:=(Tl+Tr) div 2;
if R<=m then Sum:=Sum(L, R,2*i, Tl, m)
else
if L>m then Sum:=Sum(L, R,2*i+1,m+1,Tr)
else
Sum:=Sum(L, m,2*i, Tl, m)+Sum(m+1,R,2*i+1,m+1,Tr);
end;
End;
Дерево отрезков для максимума (минимума) строится и используется аналогично. Тексты соответствующих процедур и функций будут приведены на примере решения следующей известной задачи, уже встречавшейся ранее.
Прямоугольники. На координатной плоскости задано N прямоугольников со сторонами, параллельными координатным осям. Найти площадь фигуры, получающейся в результате объединения прямоугольников.
Ввод из файла INPUT. TXT. В первой строке содержится значение N (1 ≤ N ≤ 100000). В каждой из следующих N строк – четыре целых числа Ai, Bi, Ci, Di через пробел, определяющие координаты левого верхнего и правого нижнего углов очередного прямоугольника (-109 ≤ Ai, Bi, Ci, Di ≤ 109).
Вывод в файл OUTPUT. TXT действительного числа с точностью до двух знаков после запятой – площади фигуры.
Пример
Ввод
2
5 15 25 5
0 10 20 0
Вывод
325
В [4] описано решение этой задачи для меньшей размерности. Нужно отсортировать координаты углов прямоугольников по возрастанию и использовать метод заметания. Будем продвигать вертикальную прямую слева направо, отмечая изменение длины сечения нашей фигуры по оси Y. При встрече точки, соответствующей левой стороне прямоугольника, длина сечения может увеличиться, а при встрече правой стороны прямоугольника уменьшиться. Очередная прибавка к площади составит произведение длины отрезка по оси X на длину сечения.
Длина сечения находится также методом заметания. Создадим еще один массив координат вершин прямоугольников, но уже в порядке возрастания координаты Y. Изменение длины сечения связано с добавлением или удалением отрезка по оси Y. Будем просматривать точки вершин уже в порядке возрастания по оси Y, поддерживая счетчик числа вложенных отрезков. При встрече левого конца отрезка к счетчику прибавляется единица, а на правом конце отрезка она вычитается. Если при некотором значении координаты Y счетчик оказался больше нуля, а при другом значении снова обратился в ноль, то разность значений должна добавиться в длину сечения.
Оценим трудоемкость этого метода. Быстрая сортировка координат по каждой оси имеет трудоемкость O(N log N). Для каждой новой точки по оси X потребуется перебрать точки сечения по оси Y. Общая трудоемкость метода составит O(N2). При заданной размерности описанный подход не годится.
На выручку приходит дерево отрезков. Создадим два массива, сортируя координаты углов прямоугольника по осям X и Y. В целях увеличения скорости вычислений свяжем оба массива ссылками, указав для каждого элемента одного массива соответствующий элемент другого массива.
Обозначим через Ymin и Ymax минимальное и максимальное значения координаты Y. Отрезок [Ymin; Ymax] окажется разделенным на N-1 отрезков S1, S2,…, SN-1. Каждая вертикальная сторона прямоугольника покрывает один или несколько таких отрезков.
Снова используем метод заметания, продвигая сканирующую прямую по оси X. Для каждого отрезка Si будем отмечать в счетчике Ai, сколько раз отрезок Si входит в сечение. Добавление и удаление стороны прямоугольника по оси Y, покрывающей отрезки Sk, Sk+1,…, Sm, вызовет увеличение или уменьшение на единицу счетчиков Ak, Ak+1,…, Am.
Организуем по массиву A1, A2,…, AN-1 дерево отрезков для минимума. Введем еще один дополнительный массив Lm размерности 8N и той же адресации, что и массив Q. В i-м элементе будем хранить Lm[i] – суммарную длину отрезков в дереве с корнем i, на которых достигается минимум. Значения массива Lm модифицируются при изменении дерева. Если в корне всего дерева минимум равен нулю, то значение Lm[1] определяет суммарную длину отрезков Si, не входящих в сечение по оси Y. Тогда длину сечения составит величина Ymax - Ymin - Lm[1].
Поскольку каждое изменение элементов массива Ak, Ak+1,…, Am имеет трудоемкость O(log N), общая трудоемкость алгоритма оценивается величиной O(N log N). Ниже приводится полный текст программы.
Program Rectang;
Const
MM=420;
{максимальное количество прямоугольников -
почти предел для Turbo Pascal, в Delphi возможно и 200000}
Var
i, k,N, M: longint;
S: double; {площадь объединения прямоугольников}
X1,Y1: array[1..2*MM] of longint;
{X1,Y1 - координаты верхних левых и нижних правых углов,
отсортированных по X}
Ind: array [1..2*MM] of longint;
{Ind[i]-индекс в (X1,Y1) диагональной вершины прямоугольника}
X2,Y2: array[1..2*MM] of longint;
{координаты (X1,Y1), отсортированные по Y}
Ref1: array [1..2*MM] of longint;
{Ref1[i]-индекс в массиве (X2,Y2) элемента (X1[i],Y1[i])}
Ref2: array [1..2*MM] of longint;
{Ref2[i]-индекс в массиве (X1,Y1) элемента (X2[i],Y2[i])}
{Ref1, Ref2 для быстрой связи массивов (X1,Y1) и (X2,Y2)}
Q: array [1..8*MM] of longint; {дерево минимумов для A[i]}
Add: array [1..8*MM] of longint;
{Add[i] - модифицирующая добавка ко всем сыновьям вершины i}
Lm: array [1..8*MM] of longint;
{суммарные длины отрезков, где в дереве достигается MIN}
Ch: char;
c, d,L, R,V, W,XPred: longint;
Lx, Ly, Lmax: longint;
Fin, Fout: text;
Function Min(a, b:longint):longint;
Begin
if a<b then Min:=a
else Min:=b
End;
Function Max(a, b:longint):longint;
Begin
if a>b then Max:=a
else Max:=b
End;
Procedure Sort1(L, R: longint); {быстрая сортировка по X}
Var
i, j,k, x,y, w,a, b: longint;
Begin
i:=L; { нижний индекс }
j:=R; { верхний индекс }
k:=(L+R) div 2;
x:=X1[k]; y:=Y1[k];
Repeat
While (X1[i]<x) or
((X1[i]=x) and (Y1[i]<y)) do i:=i+1;
{для одного значения X выбор по возрастанию Y позволяет
рассмотреть закрывающую сторону прямоугольника раньше}
While (X1[j]>x) or
((X1[j]=x) and (Y1[j]>y)) do j:=j-1;
if i<=j then
begin
w:=X1[i]; X1[i]:=X1[j]; X1[j]:=w;
w:=Y1[i]; Y1[i]:=Y1[j]; Y1[j]:=w;
a:=Ind[i]; b:=Ind[j];
if (a<>j) or (b<>i) then
{меняются местами не противоположные углы прямоугольника}
begin
Ind[i]:=b; Ind[j]:=a;
Ind[a]:=j; Ind[b]:=i;
end;
i:=i+1; j:=j-1
end
Until i>j;
if L<j then Sort1(L, j);
if i<R then Sort1(i, R);
End;
Procedure Sort2(L, R: longint); {быстрая сортировка по Y}
Var
i, j,y, w,a, b: longint;
Begin
i:=L; { нижний индекс }
j:=R; { верхний индекс }
y:=Y2[(L+R) div 2];
Repeat
While Y2[i]<y do i:=i+1;
While Y2[j]>y do j:=j-1;
if i<=j then
begin
w:=Y2[i]; Y2[i]:=Y2[j]; Y2[j]:=w;
w:=X2[i]; X2[i]:=X2[j]; X2[j]:=w;
a:=Ref2[i]; b:=Ref2[j];
w:=Ref2[i]; Ref2[i]:=Ref2[j]; Ref2[j]:=w;
Ref1[a]:=j; Ref1[b]:=i;
i:=i+1; j:=j-1
end
Until i>j;
if L<j then Sort2(L, j);
if i<R then Sort2(i, R);
End;
Procedure Build(i, L,R: longint);
{построение дерева минимумов по нулевому массиву}
{i - номер вершины, L - нижняя граница, R - верхняя граница
Lm[i]-сумма длин интервалов с MIN значением для i-й вершины}
Var
m: longint;
Begin
if L=R then Lm[i]:=Y2[L+1]-Y2[L]
else
begin
m:=(L+R) div 2;
Build(2*i, L,m);
Build(2*i+1,m+1,R);
Lm[i]:=0;
if Q[i]=Q[2*i] then {модифицирующих добавок сначала нет}
Lm[i]:=Lm[i]+Lm[2*i];
if Q[i]=Q[2*i+1] then
Lm[i]:=Lm[i]+Lm[2*i+1];
end;
End;
Function Minim(L, R,i, Tl, Tr:longint):longint;
{поиск минимума элементов массива по интервалу индексов}
{L, R - интервал индексов для минимума,
i – индекс корня для поиска в дереве, Tl, Tr - границы поиска}
Var
m: longint;
Begin
if (L=Tl) and (R=Tr) then Minim:=Q[i]
else
begin
m:=(Tl+Tr) div 2;
if R<=m then Minim:=Minim(L, R,2*i, Tl, m)+Add[i]
else
if L>m then Minim:=Minim(L, R,2*i+1,m+1,Tr)+Add[i]
else
Minim:=Min(Minim(L, m,2*i, Tl, m),Minim(m+1,R,2*i+1,m+1,Tr))+
Add[i];
end;
End;
Function Long(L, R,i, Tl, Tr:longint):longint;
{сумма нулевых отрезков, (L, R) - интервал индексов для поиска,
i – индекс корня для поиска в дереве,(Tl, Tr) - границы поиска}
Var
m: longint;
Begin
if (L=Tl) and (R=Tr) then
if Q[i]=0 then Long:=Lm[i] {если MIN=0}
else Long:=0
else
begin
m:=(Tl+Tr) div 2;
if R<=m then Long:=Long(L, R,2*i, Tl, m)
else
if L>m then Long:=Long(L, R,2*i+1,m+1,Tr)
else
Long:=Long(L, m,2*i, Tl, m)+Long(m+1,R,2*i+1,m+1,Tr);
end;
End;
Procedure Plus(L, R,X, i,Tl, Tr:longint);
{на отрезке (Y2[L],Y2[R]) добавление значения X в A[i] для Min,
модификация массива Lm - суммы длин отрезков с Min}
Var
m: longint;
Begin
if (L=Tl) and (R=Tr) then
begin
Q[i]:=Q[i]+X;
Add[i]:=Add[i]+X;
end
else
begin
m:=(Tl+Tr) div 2;
if R<=m then Plus(L, R,X,2*i, Tl, m)
else
if L>m then Plus(L, R,X,2*i+1,m+1,Tr)
else
begin
Plus(L, m,X,2*i, Tl, m);
Plus(m+1,R, X,2*i+1,m+1,Tr);
end;
Q[i]:=Min(Q[2*i],Q[2*i+1])+Add[i];
{Add[i]-добавка для каждого элемента в интервале
индексов вершины i, т. е. для всех потомков i}
Lm[i]:=0;
if Q[i]=Q[2*i]+Add[i] then
Lm[i]:=Lm[i]+Lm[2*i];
if Q[i]=Q[2*i+1]+Add[i] then
Lm[i]:=Lm[i]+Lm[2*i+1];
end;
End;
Begin
Assign(Fin,'input. txt');
Reset(Fin);
ReadLn(Fin, M);
N:=2*M; {количество вершин прямоугольников}
For i:=1 to M do
begin
k:=2*(i-1)+1;
ReadLn(Fin, X1[k],Y1[k],X1[k+1],Y1[k+1]);
Ind[k]:=k+1; {связь противоположных вершин прямоугольников}
Ind[k+1]:=k;
end;
Close(Fin);
Sort1(1,N); {сортировка точек (X1,Y1) по координате X}
For k:=1 to N do
begin
X2[k]:=X1[k];
Y2[k]:=Y1[k];
Ref1[k]:=k; {Ref1[i]-индекс (X1[i],Y1[i]) в массиве (X2,Y2)}
Ref2[k]:=k; {Ref2[i]-индекс (X2[i],Y2[i]) в массиве (X1,Y1)}
end;
Sort2(1,N); {сортировка точек (X2,Y2) по координате Y}
For i:=1 to 4*N do {инициализация дерева минимумов}
begin
Q[i]:=0;
Add[i]:=0;
Lm[i]:=0;
end;
Build(1,1,N-1); {построение массива Lm для нулевого дерева MIN}
XPred:=X1[1]; {предыдущая координата по х}
Ly:=0; {здесь будет длина сечения по y}
Lmax:=Y2[N]-Y2[1]; {диапазон значений по оси Y}
S:=0; {общая площадь объединения прямоугольников}
For i:=1 to N do
begin
Lx:=X1[i]-XPred; {длина очередного прямоугольника по x}
XPred:=X1[i];
V:=Y1[i]; {координаты концов нового отрезка}
W:=Y1[Ind[i]];
c:=Ref1[i];
d:=Ref1[Ind[i]]; {индексы нижней и верхней точек в (X2,Y2)}
L:=Min(c, d);
R:=Max(c, d);
if V>W then {X[i] - левая сторона прямоугольника}
Plus(L, R-1,1,1,1,N-1) {добавили отрезок}
else {X[i] - правая сторона прямоугольника}
Plus(L, R-1,-1,1,1,N-1); {убрали отрезок}
{если углы прямоугольников задаются в другом порядке: левый
нижний, а затем правый верхний, то изменение на if V<W}
S:=S+Lx*Ly; {учли пройденную площадь}
Ly:=Lmax-Long(1,N-1,1,1,N-1);
{вычли сумму длин нулевых отрезков, Ly-длина сечения по y}
end;
Assign(Fout,'output. txt');
Rewrite(Fout);
WriteLn(Fout, S:0:2);
{2 знака после запятой без ведущих пробелов}
Close(Fout);
End.
Задачи для самостоятельного решения
16.1. Скрудж – нефтяной магнат (10)
Нефтяные месторождения в Берляндии имеют очень небольшие размеры и считаются точками. В Берляндии всего N месторождений, для каждого из которых известны его координаты (Xi, Yi). Скрудж вкладывает немалые деньги в покупку месторождений. Для этого он выкупает прямоугольные участки земли, стороны которых параллельны осям координат. Покупая очередной участок, Скрудж не замечает, что часть этого участка, а возможно, и весь он, куплена им до этого. Всего он выкупил M участков, для каждого из которых известны пары координат противоположных углов. Скрудж часто задается вопросом, сколько же всего нефтяных месторождений находится на его территории. Месторождение находится на территории Скруджа, если оно расположен внутри или на границе хотя бы одного из M прямоугольников. Более того, для каждого месторождения Скрудж хочет знать количество принадлежащих ему участков, на территории которых оно находится.
Ввод из файла INPUT. TXT. В первой строке находится число N (1 ≤ N ≤ 100000). Далее в N строках заданы через пробел целочисленные координаты Xi, Yi. Два или более месторождений могут находиться в одной точке. Следующая строка содержит целое число M (1 ≤ M ≤ 100000). Далее в M строках заданы четверками целых чисел через пробел координаты левого верхнего и правого нижнего углов прямоугольников. Два или более прямоугольников могут совпадать. Прямоугольники не могут вырождаться в отрезки или точки. Все координаты не превосходят по абсолютной величине 109.
Вывод в файл OUTPUT. TXT. Выходной файл должен содержать N строк, i-я строка показывает количество участков, содержащих i-е месторождение в соответствии с их порядком во входном файле.
Примеры
Ввод 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 1 1 0
9 11 11 9
9 100 100 -1
Вывод 1 Вывод 2
1 1
1 1
2 1
0 1
16.2. Разноска пиццы (11)
В городе X все улицы параллельны координатным осям. Каждая точка с целочисленными координатами является пересечением двух улиц. Кварталы плотно застроены небоскребами, поэтому расстояние между точками (X1, Y1) и (X2, Y2) определяется как | X1 - X2 | + | Y1 - Y2 |. Компания по разноске пиццы имеет в городе N точек. Покупателям пицца приносится мальчиками, которые передвигаются с разной скоростью, поэтому для каждой пиццерии известно максимальное расстояние, на которое может быть доставлен заказ. Кризис вынуждает закрыть ряд пиццерий. Было принято решение закрыть какие-либо пиццерии из тех, которые находятся в пределах досягаемости не менее чем из K других пиццерий. Требуется выявить все пиццерии, которые могут оказаться зарытыми.
Ввод из файла INPUT. TXT. В первой строке находятся два целых числа N и K через пробел (2 ≤ N ≤ 105, 1 ≤ M ≤ N -1). Следующие N строка содержат целочисленные координаты очередной пиццерии X, Y и максимальное расстояние W для доставки пиццы (0 ≤ X, Y, W ≤ 109 ).
Вывод в файл 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, то есть преобразование сохраняет целочисленные значения координат точек и дает целочисленное значение стороны квадрата. Далее нужно применить метод сканирующей прямой и с помощью дерева отрезков с функцией суммы обработать стандартные события.
16.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
16.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
16.5. Оранжерея (12)
Оранжерея представляет собой прямоугольный участок для выращивания растений пермского периода. Оранжерея была разбита дорожками на квадраты. В центре каждого квадрата посажено одно растение. Размер квадрата зависит от корневой системы растения.
За год дорожки заросли травой, что затруднило уход за оранжереей. Чтобы при садовых работах не повредить корневую систему какого-либо растения, по имеющемуся расположению растений необходимо восстановить размеры соответствующих им квадратов.
Введем декартову прямоугольную систему координат, начало которой совмещено с левым нижним углом оранжереи. Ось Ox направлена вдоль нижней границы участка, ось Oy – вдоль левой. Изначально дорожки были проложены параллельно осям координат. Единичный отрезок удалось выбрать так, что координаты углов каждого из квадратов оказались целыми.
Требуется написать программу, которая по размеру оранжереи и координатам растений определит размеры соответствующих им квадратов.
Ввод из файла INPUT. TXT. В первой строке записаны три натуральных числа: W – ширина оранжереи, H – длина оранжереи и N – количество посаженых растений (N ≤ 2Ч105). В каждой из следующих N строк расположены по два числа: xi, yi – координаты i-го растения (0 < xi < W, 0 < yi < H, xi, yi ≤ 2Ч109). Гарантируется, что соответствующие растениям квадраты имеют целую длину стороны и покрывают всю оранжерею.
Вывод в файл 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
Примечание. Оранжерея во втором примере соответствует следующему рисунку:
Подсказка
Отсортируем центры квадратов в порядке возрастания координаты X. Организуем массив S различных координат Y точек центров. Также отсортируем его по возрастанию. В элементе Ri будем хранить, до какого значения X покрыт прямоугольник на прямой Y = Si.
Пусть выбран центр i-го квадрата (Xi, Yi). Методом бинарного поиска найдем индекс значения j в массиве S, соответствующего центру квадрата. Тогда сторона квадрата определится выражением Ai = 2 (Xi - Rj). Теперь надо обновить массив R. Для всех значений S от (Yi - Ai /2) до (Yi + Ai /2) включительно изменим значения R на Xi + Ai /2. Индексы изменяемых значений R также находятся бинарным поиском.
Использование дерева отрезков с операциями присвоения значения на отрезке и взятия максимума позволяет выполнять все операции над массивом R с трудоемкостью O(logN). Общая сложность алгоритма составляет O(NlogN).
16.6. Лотерея (9)
Владелец казино для привлечения клиентов решил проводить ежедневную лотерею. В течение дня составляется список клиентов в порядке их прихода. Каждый клиент имеет общий баланс игры, выраженный положительным или отрицательным целым числом. По списку из N клиентов формируется соответствующий список балансов A1, A2,…, AN.
Игроку сообщается значение N, после чего он задает список номеров B1, B2,…, BN-1. Из баланса с номером k =B1 вычитается следующий баланс и результат замещает баланс Ak, то есть вместо баланса Ak появляется значение Ak - Ak+1. Список балансов сдвигается на одну позицию, начиная с номера k+1. На месте k+1 оказывается значение Ak+2, на месте k+2 – значение Ak+3 и т. д. При этом список сокращается на один элемент. Далее подобная операция проводится со значениями B2, B3,…, BN-1. В результате в списке балансов окажется единственный элемент, определяющий результат игры. Требуется по спискам балансов A1, A2,…, AN и номеров B1, B2,…, BN-1 найти выигрыш или проигрыш игрока.
Ввод. В первой строке содержится N (3 ≤ N ≤ 105) – количество элементов в списке балансов. Во второй строке задаются N элементов списка балансов A1, A2,…, AN (-104 ≤ Ai ≤ 104). В третьей строке задаются N-1 номеров B1, B2,…, BN-1 (1≤ Bi ≤N - i).
Вывод. В единственной строке выводится итоговое значение.
Примеры
Ввод 1 Ввод 2
3 3
-5 3 2 2 -6 -3
1 1 2 1
Вывод 1 Вывод 2
-10 5
Пояснение. В первом примере сначала производится операция (-5) - 3 = -8, а затем (-8) - 2 = -10. Во втором примере сначала производится операция (-6) - (-3) = -3, а затем 2 - (-3) = 5.
16.7. Драконы и принцессы (9)
Рыцарь отправился в опасное путешествие. Карта пути представляет собой N ячеек, пронумерованных от 1 до N. Первоначально рыцарь находится в ячейке 1. Он посещает ячейки по возрастанию их номеров и не может пропустить какую-либо ячейку или вернуться назад.
В каждой ячейке кроме первой находится либо принцесса, либо дракон. У каждого дракона имеется богатство в виде некоторого количества золотых монет. Дракон из клетки i имеет gi монет. Рыцарь в состоянии победить любого дракона, завладев его монетами. Тем не менее, он может проследовать мимо дракона, избежав сражения.
Когда рыцарь заходит в ячейку с принцессой, она интересуется, сколько драконов он уже убил. Если это число не менее ее красоты bi, принцесса просит рыцаря жениться на ней. Как истинный джентльмен рыцарь не может отказаться. На этом его путешествие заканчивается.
Рыцарь любит принцессу, которая находится в ячейке с номером N, и мечтает жениться именно на ней. При этом он хочет собрать как можно больше золотых монет. Помогите рыцарю справиться с этой задачей.
Ввод из файла INPUT. TXT. В первой строке содержится количество ячеек N (1 ≤ N ≤ 2·105). Следующих N строк описывают ячейки от 2 до N. Если в ячейке i находится дракон, то строка содержит символ d и целое значение gi через пробел (1≤ gi ≤104). Если же в в ячейке i принцесса, то строка содержит то строка содержит символ p и целое значение Bi (1≤ bi ≤ 2·105). Гарантируется, что в ячейке N находится принцесса.
Вывод в файл OUTPUT. TXT. В первой строке вывести целое число – максимальное количество золотых монет, которое может собрать рыцарь. Во второй строке K - количество убитых драконов. Третья строка должна содержать K целых чисел через пробел - номера ячеек с драконами, которых рыцарь должен убить. Эти номера выводятся в порядке возрастания. Если имеется несколько решений, вывести любое из них. Если рыцарь не имеет возможности жениться на любимой принцессе, вывести -1.
Примеры
Ввод 1 Ввод 2
6 6
d 10 d 10
d 12 d 12
p 2 p 2
d 1 d 1
p 2 p 3
Вывод 1 Вывод 2
13 -1
2
3 5
