|
|
題目鏈接：http://poj.org/problem?id=3277
  /**//*
 題意：
給定N(N <= 40000)個矩形，求它們的面積并。
解法：
離散化+線段樹
思路：
矩形面積并的nlog(n)經(jīng)典算法。首先我們將每個矩形的縱向邊投
影到Y(jié)軸上，這樣就可以把矩形的縱向邊看成一個閉區(qū)間，用線段樹來
維護(hù)這些矩形邊的并。現(xiàn)在求的是矩形的面積并，于是可以枚舉矩形的
x坐標(biāo)，然后檢測當(dāng)前相鄰x坐標(biāo)上y方向的合法長度，兩者相乘就是其中
一塊面積，枚舉完畢后就求得了所有矩形的面積并。
我的線段樹結(jié)點描述保存了以下信息：區(qū)間的左右端點、結(jié)點所在
數(shù)組編號（因為采用靜態(tài)結(jié)點可以大大節(jié)省申請空間的時間）、該結(jié)點
被豎直線段完全覆蓋的次數(shù)Cover和當(dāng)前結(jié)點的測度。測度是指相鄰x坐
標(biāo)之間有效的y方向的長度的和（要求在該區(qū)間內(nèi)）。于是重點就在于
如何維護(hù)測度，我們將一個矩形分成兩條豎直線段來存儲，左邊的邊稱
為入邊，右邊的邊則為出邊，然后把所有這些豎直線段按照x坐標(biāo)遞增排
序，每次進(jìn)行插入操作，因為坐標(biāo)有可能不是整數(shù)，所以必須在做這些
之前將y方向的坐標(biāo)離散化到數(shù)組中，每次插入時如果當(dāng)前區(qū)間被完全覆
蓋，那么就要對Cover域進(jìn)行更新，入邊+1，出邊-1。更新完畢后判斷當(dāng)
前結(jié)點的Cover域是否大于零，如果大于零那么當(dāng)前節(jié)點的測度就是結(jié)點
管理區(qū)間在y軸上的實際長度，否則，如果是葉子節(jié)點，那么測度為0，
如果是內(nèi)部結(jié)點，那么測度的值是左右兒子測度的和。這個更新是log(n)
的，所以，總的復(fù)雜度就是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;
}
|