题目链接：http://codeforces.com/contest/610/problem/D
就是给你宽度为1的n个线段，然你求总共有多少单位的长度。
相当于用线段树求面积并，只不过宽为1，注意y和x的最大都要+1，这样才相当于求面积。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 4e5 + ;
typedef __int64 LL;
struct data {
LL x1 , x2 , y , flag;
bool operator <(const data& cmp) const {
return y < cmp.y;
}
}a[MAXN];
struct segtree {
LL l , r , lazy , val;
}T[MAXN << ];
map <LL , LL> mp;
LL x[MAXN]; void build(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r , T[p].val = T[p].lazy = ;
if(r - l == ) {
return ;
}
build(p << , l , mid);
build((p << )| , mid , r);
} void pushup(int p) {
if(T[p].lazy) {
T[p].val = (x[T[p].r] - x[T[p].l]);
}
else if(T[p].r - T[p].l == ) {
T[p].val = ;
}
else {
T[p].val = T[p << ].val + T[(p << )|].val;
}
} void updata(int p , int l , int r , int val) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
T[p].lazy += val;
pushup(p);
return ;
}
if(r <= mid) {
updata(p << , l , r , val);
}
else if(l >= mid) {
updata((p << )| , l , r , val);
}
else {
updata(p << , l , mid , val);
updata((p << )| , mid , r , val);
}
pushup(p);
} int main()
{
int n , f = , cnt = ;
LL x1 , x2 , y1 , y2;
scanf("%d" , &n);
for(int i = ; i < n ; i++) {
scanf("%I64d %I64d %I64d %I64d" , &x1 , &y1 , &x2 , &y2);
if(x1 > x2)
swap(x1 , x2);
x2++;
if(y1 > y2)
swap(y1 , y2);
y2++;
a[f].x1 = x1 , a[f].x2 = x2 , a[f].y = y1 , a[f].flag = ;
f++;
a[f].x1 = x1 , a[f].x2 = x2 , a[f].y = y2 , a[f].flag = -;
f++;
if(!mp[x1]) {
mp[x1] = ;
x[++cnt] = x1;
}
if(!mp[x2]) {
mp[x2] = ;
x[++cnt] = x2;
}
}
build( , , cnt);
sort(a , a + f);
sort(x + , x + cnt + );
for(int i = ; i < f ; i++) {
int pos = lower_bound(x + , x + cnt + , a[i].x1) - x;
a[i].x1 = pos;
pos = lower_bound(x + , x + cnt + , a[i].x2) - x;
a[i].x2 = pos;
}
LL res = ;
updata( , a[].x1 , a[].x2 , a[].flag);
for(int i = ; i < f ; i++) {
res += (LL)(a[i].y - a[i - ].y) * T[].val;
updata( , a[i].x1 , a[i].x2 , a[i].flag);
}
printf("%I64d\n" , res);
}