前言

好难啊，看官方题解都看了好久，两种方法都没想到。

Solution 1

要维护的信息

这是我一直思考的方向。直接在线算是极困难的，容易想到离线扫描。这里以从下往上扫为例，显然我们需要在扫的过程中，维护同行中的连通性，这启发我们想到并查集。但光有并查集是不够的，因为当出现横线时，横线内部会直接被竖线切割（后文会提到），所以还需维护当前行被竖线分成的块。

这里一定要区分块和并查集（我就是卡在这了）：

块：同一行中，被竖线分开的长条，切割方法如下图：

性质：同一块中的位置一定连通，也就是属于同一并查集。

并查集：维护块与块之间的连通关系，因为不同的块可能属于同一并查集！如下图：

要维护的操作

接着，考虑将加入的线段转换为操作（注意操作总个数需为 $O(k)$）：

• 出现竖直线段：当前行的某个块被切开，切开的块所属并查集不变（因为可以通过之前的行连通），如下图：

• 消失竖直线段：线段两边的块被合并，变为连通，即所属并查集也合并，如下图：

• 出现水平线段：块的切割方式不变（因为线段水平）。未被线段完全覆盖的块所属并查集也不变；被完全覆盖的块，所属并查集更新为自己，因为加上这条线段后，它与外界完全分开。

维护方式

知道了要维护的信息和操作后，就需选定合适的数据结构。

维护块：由于存在切割和合并操作，所以平衡树是最优选择。

维护连通性：显然选择并查集，维护块（也就是平衡树节点）的连通性。由于操作三，会要求把区间的并查集都修改，所以需要用到懒标记。

综上所述：用平衡树维护块（fhq-treap 或 splay），并在节点上维护 $fa$（即并查集中的父亲）和 $tag$（即记录更新当前子树 $fa$ 的操作）。时间复杂度 $O(n\log n \space \alpha(n))$。可能 set + 线段树也能做吧。

由于这种做法代码应该较难写，所以就没写。但这种做法的适用性应该较高，且是一个练习数据结构的好题。

Solution 2

式子推导

我们发现，若把四个边界也当作线段，要求的连通块其实就是平面图的面，这启发我们想到平面图欧拉公式：

$\lvert V\rvert-\lvert E\rvert+\lvert F\rvert=k+1$

其中，$\lvert V\rvert$ 为顶点数，$\lvert E\rvert$ 为边数，$\lvert F\rvert$ 为面数，$k$ 为连通分支个数。那么，要求的答案可以表示为 $ans=\lvert F\rvert-1=\lvert E\rvert-\lvert V\rvert+k$。

但是原图并非平面图，那就需将其转为平面图，其实只用把交点看作节点即可，设在原图上交点数为 $x$，线段数为 $y=n+4$，第 $i$ 条线段上有 $f_i$ 个交点。则转化到新图：

$\lvert V\rvert=x$

由于线段 $i$ 上的交点会把它分为 $f_i-1$ 段（两端无用所以不算），所以：

$\lvert E\rvert=\sum_{i=1}^y(f_i-1)=(\sum_{i=1}^yf_i)-y=2x-y$

$ans=2x-y-x+k=x-y+k$

所以只用算交点数和线段连通块数就行了。

计算方法

• 交点个数：扫描线即可。

• 线段连通块个数：考虑到连通性，仍然使用并查集。但怎么建边？仍然尝试扫描线，从下往上扫，对于竖线，则在包含它的线段树节点上加上它；对于当前的横线，使用线段树将其分解为 $O(\log n)$ 个区间，然后让横线向区间内的每条竖线连边。这样做正确性没问题，但如果横线向能连边的竖线一一连边，那边数不就是交点数吗？

• 显然需要优化，对于一条横线，向一个线段树节点内所有竖线连边，暴力连完后，这个节点内的所有竖线一定都属于同一并查集了。反正我们只关注连通性，所以只用保留节点内一条竖线即可（贪心地选择能延伸最远的），这样之后再向这个节点连边，只用向这条留下的竖线连边就可以了。

• 这样每次加竖线，会加 $O(\log n)$ 个到线段树中；每次计算横线，可以看做清空一个节点，然后加上留下的线段，也会加 $O(\log n)$ 个线段。一共加的边数为 $O(n\log n)$，时间复杂度为 $O(n\log n)$。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
inline int read()
{
	char c=getchar();
	int f=1,x=0;
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
inline void print(LL x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
const int N=2e5+5;
int w,h,n,cnt1,cnt2,m,cnt,c[N];
LL ans;
bool vis[N];
struct line{int x,s,t;}a[N],b[N];
struct addline{int x,y,v,id;}tmp[N];
inline bool cmp1(addline x,addline y){return x.y<y.y;}
inline bool cmp2(line x,line y){return x.x<y.x;}
inline void init()
{
	for(int i=1;i<=cnt2;i++) c[++m]=b[i].x;
	sort(c+1,c+1+m);
	m=unique(c+1,c+1+m)-(c+1);
	for(int i=1;i<=cnt2;i++) b[i].x=lower_bound(c+1,c+1+m,b[i].x)-c;
	for(int i=1;i<=cnt2;i++)
	{
		tmp[++cnt]={b[i].x,b[i].s,1,i};
		tmp[++cnt]={b[i].x,b[i].t+1,-1,i};
	}
	sort(tmp+1,tmp+1+cnt,cmp1);
	sort(a+1,a+1+cnt1,cmp2);
}
struct BIT
{
	int tr[N];
	inline int lowbit(int x){return x&(-x);}
	inline void update(int x,int y){while(x<=m) tr[x]+=y,x+=lowbit(x);}
	inline int query(int x)
	{
		int res=0;
		while(x) res+=tr[x],x-=lowbit(x);
		return res;
	}
}tr;
inline void calc1()
{
	int now=1;
	for(int i=1;i<=cnt1;i++)
	{
		while(now<=cnt&&tmp[now].y<=a[i].x) tr.update(tmp[now].x,tmp[now].v),now++;
		int l=lower_bound(c+1,c+1+m,a[i].s)-c-1;
		int r=upper_bound(c+1,c+1+m,a[i].t)-c-1;
		if(l>=r) continue;
		ans+=tr.query(r)-tr.query(l);
	}
}
struct dsu
{
	int fa[N];
	inline void init(){for(int i=1;i<=n+4;i++) fa[i]=i;}
	int findfa(int x)
	{
		if(x==fa[x]) return x;
		return fa[x]=findfa(fa[x]);
	}
	inline void merge(int x,int y)
	{
		x=findfa(x);
		y=findfa(y);
		if(x==y) return;
		ans--;
		fa[y]=x;
	}
}d;
struct Segment_Tree
{
	vector<int> tr[N<<2];
	void update(int p,int s,int t,int x,int y)
	{
		tr[p].push_back(y);
		if(s==t) return;
		int mid=(s+t)>>1;
		if(x<=mid) update(p<<1,s,mid,x,y);
		else update(p<<1|1,mid+1,t,x,y);
	}
	void add(int u,int p)
	{
		int o=0;
		for(auto it=tr[p].begin();it!=tr[p].end();it++)
		{
			int v=*it;
			if(!vis[v]) continue;
			if(b[v].t>=b[o].t) o=v;
			d.merge(u,v);
		}
		tr[p].clear();
		if(o) tr[p].push_back(o);
	}
	void query(int p,int s,int t,int l,int r,int u)
	{
		if(s>=l&&t<=r)
		{
			add(u,p);
			return;
		}
		int mid=(s+t)>>1;
		if(l<=mid) query(p<<1,s,mid,l,r,u);
		if(r>mid) query(p<<1|1,mid+1,t,l,r,u);
	}
}tr2;
inline void calc2()
{
	int now=1;
	d.init();
	for(int i=1;i<=cnt1;i++)
	{
		while(now<=cnt&&tmp[now].y<=a[i].x)
		{
			int o=tmp[now].id;
			if(tmp[now].v>0) tr2.update(1,1,m,tmp[now].x,o),vis[o]=true;
			else vis[o]=false;
			now++;
		}
		int l=lower_bound(c+1,c+1+m,a[i].s)-c;
		int r=upper_bound(c+1,c+1+m,a[i].t)-c-1;
		if(l>r) continue;
		tr2.query(1,1,m,l,r,i+cnt2);
	}
}
int main()
{
	w=read();
	h=read();
	n=read();
	a[++cnt1]={0,0,w};
	a[++cnt1]={h,0,w};
	b[++cnt2]={0,0,h};
	b[++cnt2]={w,0,h};
	for(int i=1;i<=n;i++)
	{
		int sx,sy,tx,ty;
		sx=read();
		sy=read();
		tx=read();
		ty=read();
		if(sy==ty) a[++cnt1]={sy,sx,tx};
		else b[++cnt2]={sx,sy,ty};
	}
	init();
	calc1();
	calc2();
	print(ans);
	return 0;
}