|
|
题目链接：http://poj.org/problem?id=3277
  /**//*
 题意：
给定N(N <= 40000)个矩形，求它们的面积并。
解法：
离散化+线段树
思路：
矩形面积并的nlog(n)经典算法。首先我们将每个矩形的纵向边投
影到Y轴上，这样就可以把矩形的纵向边看成一个闭区间，用线段树来
维护这些矩形边的并。现在求的是矩形的面积并，于是可以枚举矩形的
x坐标，然后检测当前相邻x坐标上y方向的合法长度，两者相乘就是其中
一块面积，枚举完毕后就求得了所有矩形的面积并。
我的线段树结点描述保存了以下信息：区间的左右端点、结点所在
数组编号（因为采用静态结点可以大大节省申请空间的时间）、该结点
被竖直线段完全覆盖的次数Cover和当前结点的测度。测度是指相邻x坐
标之间有效的y方向的长度的和（要求在该区间内）。于是重点就在于
如何维护测度，我们将一个矩形分成两条竖直线段来存储，左边的边称
为入边，右边的边则为出边，然后把所有这些竖直线段按照x坐标递增排
序，每次进行插入操作，因为坐标有可能不是整数，所以必须在做这些
之前将y方向的坐标离散化到数组中，每次插入时如果当前区间被完全覆
盖，那么就要对Cover域进行更新，入边+1，出边-1。更新完毕后判断当
前结点的Cover域是否大于零，如果大于零那么当前节点的测度就是结点
管理区间在y轴上的实际长度，否则，如果是叶子节点，那么测度为0，
如果是内部结点，那么测度的值是左右儿子测度的和。这个更新是log(n)
的，所以，总的复杂度就是nlog(n)。
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 100010
#define ll __int64
struct VLine  {
int x, y0, y1;
int v;
  VLine() {}
VLine(int _x, int _y0, int _y1, int _v) {
x = _x;
y0 = _y0;
y1 = _y1;
v = _v;
 }
};
int cmp(VLine a, VLine b) {
return a.x < b.x;
}
vector< VLine > Vl;
int tmp[maxn], size, tot;
int n;
int Binary(int val) {
int l = 0;
int r = tot-1;
while(l <= r) {
int m = (l + r) >> 1;
if(tmp[m] == val)
return m;
if(val > tmp[m]) {
l = m + 1;
}else
r = m - 1;
}
}
struct Tree {
int l, r, root;
int nCover;
int ylen;
void Update();
}T[maxn*4];
void Tree::Update() {
if(nCover) {
ylen = tmp[r] - tmp[l];
}else {
if(l + 1 == r)
ylen = 0;
else
ylen = T[root<<1].ylen + T[root<<1|1].ylen;
}
}
void Build(int root, int l, int r) {
T[root].l = l;
T[root].r = r;
T[root].root = root;
T[root].nCover = T[root].ylen = 0;
if(l + 1 == r)
return ;
int mid = (l + r) >> 1;
Build(root<<1, l, mid);
Build(root<<1|1, mid, r);
}
void Insert(int root, int l, int r, int val) {
if(l >= T[root].r || T[root].l >= r)
return ;
if(l <= T[root].l && T[root].r <= r) {
T[root].nCover += val;
T[root].Update();
return ;
}
Insert(root<<1, l, r, val);
Insert(root<<1|1, l, r, val);
T[root].Update();
}
int main() {
int i;
while(scanf("%d", &n) != EOF) {
Vl.clear();
size = tot = 0;
tmp[size++] = 0;
for(i = 0; i < n; i++) {
int x0, x1, y;
scanf("%d %d %d", &x0, &x1, &y);
Vl.push_back(VLine(x0, 0, y, 1));
Vl.push_back(VLine(x1, 0, y, -1));
tmp[size++] = y;
}
sort(Vl.begin(), Vl.end(), cmp);
sort(tmp, tmp + size);
for(i = 0; i < size; i++) {
if(!i || tmp[i] != tmp[i-1]) {
tmp[tot++] = tmp[i];
}
}
ll ans = 0;
Build(1, 0, tot-1);
for(i = 0; i < Vl.size(); i++) {
if(i) {
ans += (ll)(Vl[i].x - Vl[i-1].x) * T[1].ylen;
}
Insert(1, Binary(Vl[i].y0), Binary(Vl[i].y1), Vl[i].v);
}
printf("%I64d\n", ans);
}
return 0;
}
|