城市地平线

Description

在一条水平线上有N个建筑物，建筑物都是长方形的，且可以互相遮盖。给出每个建筑物的左右坐标值Ai,Bi以及每个建筑物的高度Hi，需要计算出这些建筑物总共覆盖的面积。

Input

第一行为建筑物的个数N（1<=N<=40000），第二行到第N+1行为每个建筑物的左右坐标值Ai，Bi（1<=Ai<Bi<=1000000000）和建筑物的高度Hi（1<=Hi<=1000000000）。

Output

总面积S。

Sample Input

5
1 5 10
2 6 30
3 7 20
4 6 15
5 10 5

Sample Output

165

#include <iostream>using namespace std;#define MAXN 40001struct Line
{int x1, x2, height;
}line[MAXN];struct Node
{int l, r, col;long long len;
};int temp[MAXN * 2];
int ans[MAXN * 2];bool cmp(Line a, Line b)
{return a.height > b.height;
}class SGtree
{public:Node node[MAXN << 2];void Maketree(int i, int l, int r);void Update(int i, int x, int y, int val);
}tree;void SGtree::Maketree(int i, int l, int r)
{node[i].l = l;node[i].r = r;int mid = (l + r) >> 1;if (l + 1 == r){return ;}Maketree(i * 2, l, mid);Maketree(i * 2 + 1, mid, r);
}void SGtree::Update(int i, int x, int y, int val)
{int l = node[i].l;int r = node[i].r;if (temp[l] == x && temp[r] == y){node[i].col = 1;node[i].len = (temp[r] - temp[l]);return ;}if (node[i].col){node[i * 2].col = node[i * 2 + 1].col = node[i].col;node[i].col = 0;node[i * 2].len = temp[node[i * 2].r] - temp[node[i * 2].l];node[i * 2 + 1].len = temp[node[i * 2 + 1].r] - temp[node[i * 2 + 1].l];}int mid = temp[(l + r) >> 1];if (y <= mid){Update(i * 2, x, y, val);       }else if (x >= mid){Update(i * 2 + 1, x, y, val);   }else{Update(i * 2, x, mid, val);Update(i * 2 + 1, mid, y, val); }node[i].len = node[i * 2].len + node[i * 2 + 1].len;
}void input()
{int n, x1, x2, height, cnt = 0;cin >> n;for (int i = 0; i < n; i++){scanf("%d %d %d", &x1, &x2, &height);line[i].x1 = x1;ans[cnt++] = x1;line[i].x2 = x2;ans[cnt++] = x2;line[i].height = height;}sort(line, line + n, cmp);sort(ans, ans + cnt);int flag = -1;int total = -1;for (int i = 0; i < cnt; i++){if (ans[i] != flag){flag = ans[i];total++;}temp[total] = ans[i];}tree.Maketree(1, 0, total);long long sum = 0;for (int i = 0; i < n; i++){tree.Update(1, line[i].x1, line[i].x2, 1);if (i != n - 1){sum += (long long)(line[i].height - line[i + 1].height) * tree.node[1].len;}else{sum += (long long)line[i].height * tree.node[1].len;}}cout << sum << endl;
}int main()
{input();return 0;
}