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

Прямоугольники. На координатной плоскости задано N прямоугольников со сторонами, параллельными координатным осям. Найти площадь фигуры, получающейся в результате объединения прямоугольников.

Ввод из файла INPUT.TXT. В первой строке содержится значение N (1 ≤ N ≤ 100000). В каждой из следующих N строк – четыре целых числа A_i, B_i, C_i, D_i через пробел, определяющие координаты левого верхнего и правого нижнего углов очередного прямоугольника (-10⁹ ≤ A_i, B_i, C_i, D_i ≤ 10⁹).

Вывод в файл 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(N²). При заданной размерности описанный подход не годится.

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

Обозначим через Y_min и Y_max минимальное и максимальное значения координаты Y. Отрезок [Y_min; Y_max] окажется разделенным на N-1 отрезков S₁, S₂,…, S_N-1. Каждая вертикальная сторона прямоугольника покрывает один или несколько таких отрезков.

Снова используем метод заметания, продвигая сканирующую прямую по оси X. Для каждого отрезка S_i будем отмечать в счетчике A_i, сколько раз отрезок S_i входит в сечение. Добавление и удаление стороны прямоугольника по оси Y, покрывающей отрезки S_k, S_k+1,…, S_m, вызовет увеличение или уменьшение на единицу счетчиков A_k, A_k+1,…, A_m.

Организуем по массиву A₁, A₂,…, A_N-1 дерево отрезков для минимума. Введем еще один дополнительный массив Lm размерности 2N – 1 и той же адресации, что и массив T. В i-м элементе будем хранить Lm[i] – суммарную длину отрезков в дереве с корнем i, на которых достигается минимум. Значения массива Lm модифицируются при изменении дерева. Если в корне всего дерева минимум равен нулю, то значение Lm[1] определяет суммарную длину отрезков S_i, не входящих в сечение по оси Y. Тогда длину сечения составит величина Y_max - Y_min - Lm[1].

Поскольку каждое изменение элементов массива A_k, A_k+1,…, A_m имеет трудоемкость 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.

Задачи для самостоятельного решения

15.1. Скрудж – нефтяной магнат (12)

Нефтяные месторождения в Берляндии имеют очень небольшие размеры и считаются точками. В Берляндии всего N месторождений, для каждого из которых известны его координаты (X_i, Y_i). Скрудж вкладывает немалые деньги в покупку месторождений. Для этого он выкупает прямоугольные участки земли, стороны которых параллельны осям координат. Покупая очередной участок, Скрудж не замечает, что часть этого участка, а возможно, и весь он, куплена им до этого. Всего он выкупил M участков, для каждого из которых известны пары координат противоположных углов. Скрудж часто задается вопросом, сколько же всего нефтяных месторождений находится на его территории. Месторождение находится на территории Скруджа, если оно расположен внутри или на границе хотя бы одного из M прямоугольников. Более того, для каждого месторождения Скрудж хочет знать количество принадлежащих ему участков, на территории которых оно находится.

Ввод из файла INPUT.TXT. В первой строке находится число N (1   N  100000). Далее в N строках заданы через пробел целочисленные координаты X_i, Y_i. Два или более месторождений могут находиться в одной точке. Следующая строка содержит целое число M (1   M  100000). Далее в M строках заданы четверками целых чисел через пробел координаты левого верхнего и правого нижнего углов прямоугольников. Два или более прямоугольников могут совпадать. Прямоугольники не могут вырождаться в отрезки или точки. Все координаты не превосходят по абсолютной величине 10⁹.

Вывод в файл OUTPUT.TXT. Выходной файл должен содержать N строк, i-я строка показывает количество участков, содержащих i-е месторождение в соответствии с их порядком во входном файле.