題意：給你n個矩形， 求這n個矩形所覆蓋的面積（重復覆蓋算一次）
思路：我們可以考慮， 將y坐標保存並排序。 按x坐標離散化後建立線段樹。 每次遇到一個矩形的下底邊就將這個區間+1，表示這個區間已經被幾條線段覆蓋了。 遇到上邊就-1， 每次更新後累加當前x坐標總區間被覆蓋的長度乘以相鄰兩邊的高度。 具體原因可以畫圖看看就明白了。 另外很重要的一點就是， 線段樹都是維護一個點集， 但是對於邊的問題就會變得很麻煩， 我們可以按照區間左端點建立線段樹， 那麼一個點表示的就不是點了， 而是起點在這個點的一個線段。 這樣的話， 右區間就要相應的-1， 例如更新區間[1, 4]， 就相當於更新標號為[1, 3]的線段。
這也是處理線段覆蓋問題的通用方法。
細節參見代碼：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 100000 + 10;
int T,n,m,kase=0,addv[maxn<<2];
double sum[maxn<<2],c[maxn];
struct node {
double xl, xr, h;
int id;
node(double xl=0, double xr=0, double h=0, int id=0):xl(xl),xr(xr),h(h),id(id) {}
bool operator < (const node& rhs) const {
return h < rhs.h;
}
}b[maxn];
void PushUp(int l, int r, int o) {
if(addv[o]) sum[o] = c[r+1] - c[l]; //當前區間被線段覆蓋
else if(l == r) sum[o] = 0; // 已經到了葉子結點且沒有被覆蓋
else sum[o] = sum[o<<1] + sum[o<<1|1]; // 沒有完全被覆蓋， 但是還沒到葉子結點， 從其子區間中獲得信息
}
void build(int l, int r, int o) {
int m = (l + r) >> 1;
addv[o] = 0;
sum[o] = 0;
if(l == r) return ;
build(l, m, o<<1);
build(m+1, r, o<<1|1);
}
void update(int L, int R, int x, int l, int r, int o) {
int m = (l + r) >> 1;
if(L <= l && r <= R) {
addv[o] += x;
PushUp(l, r, o);
return ;
}
if(L <= m) update(L, R, x, l, m, o<<1);
if(m < R) update(L, R, x, m+1, r, o<<1|1);
PushUp(l, r, o);
}
double xl, xr, yl, yr;
int main() {
while(~scanf("%d",&n) && n) {
int cnt = 0, res = 0;
for(int i=0;i<n;i++) int="" m="unique(c+1," -="" c="" double="" ans="0;" i="1;i<cnt;i++)" xl="lower_bound(c+1," xr="lower_bound(c+1," test="" case="" total="" explored="" area:="" return="" pre=""><p>
</p>
</n;i++)></queue></map></deque></list></set></cmath></cstdlib></bitset></stack></vector></string></iostream></algorithm></cstring></cstdio>
