7747. Городской горизонт

 

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

Весь горизонт представлен числовой прямой с n зданиями. Силуэт i-го здания распростерся вдоль горизонта между точками ai и bi и имеет высоту hi. Определите площадь в квадратных единицах общего силуэта, образованного всеми n зданиями.

 

Вход. Первая строка содержит целое число n (1 ≤ n ≤ 40000). Каждая из следующих n строк описывает здание i тремя целыми числами: ai, bi (1 ≤ ai < bi ≤ 109) и hi (1 ≤ hi ≤ 109).

 

Выход. Выведите общую площадь городского силуэта в квадратных единицах, образованного всеми n зданиями.

 

Пример входа

Пример выхода

4

2 5 1

9 10 4

6 8 2

4 6 3

16

 

 

РЕШЕНИЕ

заметающая прямая

 

Анализ алгоритма

Рассмотрим все точки – абсциссы начал и концов зданий – и отсортируем их по возрастанию. Для каждой такой точки будем хранить:

·        её координату,

·        тип (начало здания – type = 0, конец – type = 1),

·        высоту соответствующего здания.

Далее будем последовательно обрабатывать эти точки слева направо.

 

В мультимножестве s будем хранить высоты зданий, уже начавшихся, но ещё не завершившихся к текущему моменту. Это мультимножество позволяет быстро находить максимальную высоту среди активных зданий.

 

Пусть текущая точка имеет координату xi, а следующая xi+1. Обозначим через h максимальный элемент в мультимножестве s (если множество пусто, считаем h = 0). Тогда на интервале [xi, xi+1]) максимальная высота силуэта равна h, и вклад в площадь равен

 

(xi+1 – xi) * h

Добавим это значение к общей площади.

После этого обновим мультимножество:

·        если точка xi является началом здания, добавим его высоту в s;

·        если это конец здания, удалим соответствующую высоту из s.

Порядок обработки событий с одинаковыми абсциссами (начал и концов зданий) не влияет на корректность решения, так как площадь на отрезке нулевой длины не учитывается.

 

Пример

 

Реализация алгоритма

Для представления точки введём структуру node, которая будет хранить её абсциссу x, признак того, является ли она началом (type = 0) или концом (type = 1) отрезка, а также высоту h соответствующего здания.

 

struct node

{

  int x, type, h;

  node(int x, int type, int h) : x(x), type(type), h(h) {};

};

 

Определим компаратор f для точек – будем сортировать их по возрастанию абсциссы.

 

int f(node a, node b)

{

  return a.x < b.x;

}

 

Объявим массив точек Event, а также мультимножество s для хранения высот зданий, пересекающихся с текущим положением сканирующей прямой.

 

vector<node> Event;

multiset<int, greater<int> > s;

 

Читаем входные данные. Строим массив точек.

 

scanf("%d",&n);

for(i = 0; i < n; i++)

{

  scanf("%d %d %d",&left,&right,&height);

  Event.push_back(node(left,0,height));

  Event.push_back(node(right,1,height));

}

 

Сортируем массив точек по неубыванию абсцисс.

 

sort(Event.begin(),Event.end(),f);

 

В переменной res будем накапливать общую площадь городского силуэта.

 

res = 0;

 

Двигаемся слева направо по точкам массива Event. Для каждого значения i в цикле for рассматриваем инервал (Event[i].x, Event[i + 1].x).

 

for (i = 0; i < Event.size() - 1; i++)

{

 

Если точка xi является началом здания, добавим соответствующую высоту в мультимножество.

 

  int h = Event[i].h;

  if (Event[i].type == 0) s.insert(h);

 

Если точка xi является концом здания, удалим соответствующую ей высоту из мультимножества.

 

  else s.erase(s.find(h));

 

Если мультимножество не пусто, то на отрезке между точками Event[i].x и Event[i + 1].x существует линия горизонта, высота которой равна максимальному элементу в s, то есть значению *s.begin().

 

  if (!s.empty())

    res += 1LL * *s.begin() * (Event[i+1].x - Event[i].x);

}

 

Выводим искомую площадь.

 

printf("%lld\n",res);

 

Реализация при помощи дерева отрезков

Выполним сжатие координат абсцисс зданий с помощью отображения mp (например, mp[2] = 1, mp[4] = 2 и так далее). Затем построим дерево отрезков на диапазоне [1..len], где len ≤ 40000.

 

Каждый лист дерева отрезков соответствует одному элементарному (неделимому) интервалу силуэта на горизонте. Например, вершина 1 соответствует интервалу [2; 4], вершина 2 соответствует интервалу [4; 5]. Тогда отрезок [a, b] покрывается вершинами дерева отрезков с индексами [mp[a], mp[b] – 1]. Например, отрезок [2; 5] покрывается вершинами [mp[2], mp[5] – 1] = [1, 2].

Для каждого здания на отрезке [ai, bi] с высотой hi увеличим на hi значения дерева отрезков на интервале [mp[ai], mp[bi] – 1]. При проталкивании значений в вершинах будем поддерживать максимум:

Протолкнём все значения из внутренних вершин к листьям, после чего в листьях будут храниться высоты силуэта на соответствующих интервалах. Например, первый лист соответствует отрезку [2; 4] и содержит значение 1, второй лист соответствует отрезку [4; 5] и содержит значение 3 и так далее. Последняя вершина дерева отрезков не соответствует ни одному интервалу и является фиктивной.

 

#include <cstdio>

#include <cstring>

#include <set>

#include <map>

#include <vector>

#include <algorithm>

#define MAX 80010

using namespace std;

 

int SegTree[4*MAX];

vector<int> a;

map<int,int> mp;

int i, n, l, r, h, len;

long long res;

struct Building

{

  int left, right, height;

} b[40010];

 

void Push(int Vertex, int LeftPos, int Middle, int RightPos)

{

  if (SegTree[Vertex])

  {

    SegTree[2*Vertex] = max(SegTree[2*Vertex],SegTree[Vertex]);

    SegTree[2*Vertex+1] = max(SegTree[2*Vertex+1],SegTree[Vertex]);

    SegTree[Vertex] = 0;

  }

}

 

void Add(int Vertex, int LeftPos, int RightPos,

         int Left, int Right, int x)

{

  if (Left > Right) return;

  if ((LeftPos == Left) && (RightPos == Right))

    SegTree[Vertex] = max(SegTree[Vertex],x);

  else

  {

    int Middle = (LeftPos + RightPos) / 2;

    Push(Vertex,LeftPos,Middle,RightPos);

 

    Add(2*Vertex, LeftPos, Middle, Left, min(Middle,Right), x);

    Add(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right, x);

  }

}

 

long long Count(int Vertex, int LeftPos, int RightPos)

{

  if (LeftPos == RightPos)

    return 1LL * SegTree[Vertex] * (a[LeftPos+1] - a[LeftPos]);

  else

  {

    int Middle = (LeftPos + RightPos) / 2;

    Push(Vertex,LeftPos,Middle,RightPos);

 

    return Count(2*Vertex, LeftPos, Middle) +

           Count(2*Vertex+1, Middle+1, RightPos);

  }

}

 

int main(void)

{

  scanf("%d",&n);

  memset(SegTree,0,sizeof(SegTree));

  set<int> s;

  for(i = 1; i <= n; i++)

  {

    scanf("%d %d %d",&b[i].left,&b[i].right,&b[i].height);

    s.insert(b[i].left); s.insert(b[i].right);

  }

  len = s.size(); a.resize(len+2);

  copy(s.begin(),s.end(),a.begin()+1);

  for(i = 1; i <= len; i++) mp[a[i]] = i;

 

  for(i = 1; i <= n; i++)

    Add(1,1,len,mp[b[i].left],mp[b[i].right]-1,b[i].height);

 

  res = Count(1,1,len);

  printf("%lld\n",res);

  return 0;

}