Description：

求矩形面积并。

$1\leqslant n\leqslant10^4$

Solution：

矩形面积并有经典的线段树做法，具体做法是每个点维护一个 $cnt$ 表示这个区间被覆盖了多少次， $len$ 表示覆盖长度，如果 $cnt>0$ 则 $len=r-l+1$ ，否则 $len$ 等于左右儿子 $len$ 之和，每次插入前计算一下这个和上一个之间的距离差乘一下根节点被覆盖长度即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 10010

struct scan

{

	int top,bot,pos,tag;

}s[MAXN << 1];

int tot = 0;

bool cmp_pos(scan a,scan b){return a.pos < b.pos;}

#define MAX 100010

struct node

{

	int lc,rc;

	int len,cnt;

	node(){len = cnt = 0;}

}t[MAX << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].cnt += k;

		if(t[rt].cnt > 0)t[rt].len = r - l + 1;

		else t[rt].len = t[t[rt].lc].len + t[t[rt].rc].len;

		return;

	}

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	if(t[rt].cnt > 0)t[rt].len = r - l + 1;

	else t[rt].len = t[t[rt].lc].len + t[t[rt].rc].len;

	return;

}

int main()

{

	scanf("%d",&n);

	build(root,0,100000);

	int r1,c1,r2,c2;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d%d",&r1,&c1,&r2,&c2);

		if(c1 > c2)swap(c1,c2);

		if(r1 > r2)swap(r1,r2);

		if(r1 == r2)

		{

			s[++tot] = (scan){c2,c1,r1 - 1,1};

			s[++tot] = (scan){c2,c1,r1 + 1,-1};

		}

		else

		{

			s[++tot] = (scan){c1 + 1,c1 - 1,r1,1};

			s[++tot] = (scan){c1 + 1,c1 - 1,r2,-1};

		}

	}

	sort(s + 1,s + 1 + tot,cmp_pos);

	long long ans = 0;

	for(int i = 1;i <= tot;++i)

	{

		if(i != 1)ans += 1ll * t[root].len * (s[i].pos - s[i - 1].pos);

		add(root,s[i].bot,s[i].top - 1,s[i].tag,0,100000);

	}

	cout << ans << endl;

	return 0;

}