矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结）

26 Feb 2019 6579字 22分次 ACM, 扫描线, and 线段树
如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）

跟着这篇博客复习扫描线+线段树…

Atlantis

求矩形并，即平面上至少被一个矩形覆盖的面积。

离散化: 这些技巧都是老生常谈的了，不然浮点数怎么建树，离散化 x 坐标就可以了。
扫描线: 首先把矩形按 y 轴分成两条边，上边和下边，对 x 轴建树，扫描线可以看成一根平行于 x 轴的直线。从 y=0 开始往上扫，下边表示要计算面积+1，上边表示已经扫过了 −1，直到扫到最后一条平行于 xx 轴的边但是真正在做的时候，不需要完全模拟这个过程，一条一条边地插入线段树就好了。
线段树: 用于动态维护扫描线在往上走时，x 轴哪些区域是有合法面积的。这种线段树是不用懒标记的，因为没有查询操作

#include <bits/stdc++.h>
using namespace std;
typedef double ll;
struct Ranker : vector<ll>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct AreaUnion
{
	struct Seg
	{
		ll l, r, h;
		int f;
		bool operator<(const Seg &rhs) const { return h < rhs.h; }
	};
	struct Node
	{
		int cnt;
		ll sum;
	};
	vector<Seg> s;
	vector<Node> v;
	Ranker rk;
	void add(ll l, ll b, ll r, ll t)
	{
		rk.push_back(l);
		rk.push_back(r);
		s.push_back({l, r, b, 1});
		s.push_back({l, r, t, -1});
	}
	void upd(int ql, int qr, int c, int l, int r, int rt = 1)
	{
		if (ql <= l && r <= qr)
			v[rt].cnt += c;
		else
		{
			int m = l + r >> 1;
			if (ql <= m)
				upd(ql, qr, c, l, m, rt << 1);
			if (qr > m)
				upd(ql, qr, c, m + 1, r, rt << 1 | 1);
		}
		v[rt].sum = v[rt].cnt ? rk[r + 1] - rk[l] : l < r ? v[rt << 1].sum + v[rt << 1 | 1].sum : 0;
	}
	ll ask()
	{
		rk.init();
		sort(s.begin(), s.end());
		v.assign(rk.size() * 4, Node());
		ll ans = 0;
		for (int i = 0; i + 1 < s.size(); ++i)
		{
			upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
			ans += v[1].sum * (s[i + 1].h - s[i].h);
		}
		return ans;
	}
};
int main()
{
	for (int kase = 0, n; ~scanf("%d", &n) && n;)
	{
		AreaUnion a;
		for (int i = 0; i < n; ++i)
		{
			ll l, b, r, t;
			scanf("%lf%lf%lf%lf", &l, &b, &r, &t);
			a.add(l, b, r, t);
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++kase, a.ask());
	}
}

覆盖的面积

题目链接

求矩形交，即平面上至少被覆盖两次的面积。线段树上维护被覆盖一次的长度和被覆盖两次的长度。

前面的与矩形面积并类似，不同的是要考虑至少覆盖一次 one 和至少覆盖两次 two 的更新。
尤其是当前被覆盖了一次的时候，由于没有 down 操作，父亲节点的信息是没有同步到儿子节点的，这样的话 up 就要考虑了。
父亲被记录覆盖了一次，但是如果儿子被覆盖过，这些操作都是在这个父亲这个大区间上的，就相当于父亲区间被覆盖了至少两次，所以 two 和 one 都要更新。

#include <bits/stdc++.h>
using namespace std;
typedef double ll;
struct Ranker : vector<ll>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct AreaIntersection
{
	struct Seg
	{
		ll l, r, h;
		int f;
		bool operator<(const Seg &rhs) const { return h < rhs.h; }
	};
	struct Node
	{
		int cnt;
		ll one, two;
	};
	vector<Seg> s;
	vector<Node> v;
	Ranker rk;
	void add(ll l, ll b, ll r, ll t)
	{
		rk.push_back(l);
		rk.push_back(r);
		s.push_back({l, r, b, 1});
		s.push_back({l, r, t, -1});
	}
	void upd(int ql, int qr, int c, int l, int r, int rt = 1)
	{
		if (ql <= l && r <= qr)
			v[rt].cnt += c;
		else
		{
			int m = l + r >> 1;
			if (ql <= m)
				upd(ql, qr, c, l, m, rt << 1);
			if (qr > m)
				upd(ql, qr, c, m + 1, r, rt << 1 | 1);
		}
		if (v[rt].cnt == 0)
		{
			v[rt].one = l != r ? v[rt << 1].one + v[rt << 1 | 1].one : 0;
			v[rt].two = l != r ? v[rt << 1].two + v[rt << 1 | 1].two : 0;
		}
		else
		{
			v[rt].one = rk[r + 1] - rk[l];
			if (v[rt].cnt > 1)
				v[rt].two = rk[r + 1] - rk[l];
			else
				v[rt].two = l != r ? v[rt << 1].one + v[rt << 1 | 1].one : 0;
		}
	}
	ll ask()
	{
		rk.init();
		sort(s.begin(), s.end());
		v.assign(rk.size() * 4, Node());
		ll ans = 0;
		for (int i = 0; i + 1 < s.size(); ++i)
		{
			upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
			ans += v[1].two * (s[i + 1].h - s[i].h);
		}
		return ans;
	}
};
int main()
{
	int t, n;
	for (scanf("%d", &t); t--;)
	{
		AreaIntersection a;
		scanf("%d", &n);
		for (ll l, b, r, t; n--;)
		{
			scanf("%lf%lf%lf%lf", &l, &b, &r, &t);
			a.add(l, b, r, t);
		}
		printf("%.2lf\n", a.ask());
	}
}

Picture

题目链接

求矩形周长并。

解法一

可以用类似矩形面积并的办法，不过这次我们，不算面积罢了。
需要注意的是，由于周长的线会被重复覆盖，每次需要和上一次的作差。
但是这样仅仅是 x 轴的，不过可以再对 y 轴做一次加起来就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Ranker : vector<ll>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct HalfPerimeter
{
	struct Seg
	{
		ll l, r, h;
		int f;
		bool operator<(const Seg &rhs) const { return h != rhs.h ? h < rhs.h : f > rhs.f; }
	};
	struct Node
	{
		int cnt;
		ll sum;
	};
	vector<Seg> s;
	vector<Node> v;
	Ranker rk;
	ll add(ll l, ll b, ll r, ll t)
	{
		rk.push_back(l);
		rk.push_back(r);
		s.push_back({l, r, b, 1});
		s.push_back({l, r, t, -1});
	}
	void upd(int L, int R, int c, int l, int r, int rt = 1)
	{
		if (L <= l && r <= R)
			v[rt].cnt += c;
		else
		{
			int m = l + r >> 1;
			if (L <= m)
				upd(L, R, c, l, m, rt << 1);
			if (R > m)
				upd(L, R, c, m + 1, r, rt << 1 | 1);
		}
		v[rt].sum = v[rt].cnt ? rk[r + 1] - rk[l] : l != r ? v[rt << 1].sum + v[rt << 1 | 1].sum : 0;
	}
	ll ask()
	{
		rk.init();
		sort(s.begin(), s.end());
		v.assign(rk.size() << 2, Node());
		ll ans = 0;
		for (int i = 0; i < s.size(); ++i)
		{
			ll last = v[1].sum;
			upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
			ans += abs(v[1].sum - last);
		}
		return ans;
	}
};
int main()
{
	for (int n; ~scanf("%d", &n);)
	{
		HalfPerimeter x, y;
		for (int i = 0, l, b, r, t; i < n; ++i)
		{
			scanf("%d%d%d%d", &l, &b, &r, &t);
			x.add(l, b, r, t);
			y.add(b, l, t, r);
		}
		printf("%d\n", x.ask() + y.ask());
	}
}

解法二

也可以只对 x 轴做一次扫描线，只要同时维护 y 轴竖线（就是求矩形面积并的时候的高）的个数 vtl。
需要的注意的是竖线重合的情况，需要再开变量 lbd、rbd 来判断重合，避免重复计算。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Ranker : vector<ll>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct Perimeter
{
	struct Seg
	{
		ll l, r, h;
		int f;
		bool operator<(const Seg &rhs) const { return h < rhs.h; }
	};
	struct Node
	{
		int cnt;
		ll sum, vtl, lbd, rbd;
	};
	vector<Seg> s;
	vector<Node> v;
	Ranker rk;
	void add(ll l, ll b, ll r, ll t)
	{
		rk.push_back(l);
		rk.push_back(r);
		s.push_back({l, r, b, 1});
		s.push_back({l, r, t, -1});
	}
	void upd(int ql, int qr, int c, int l, int r, int rt = 1)
	{
		if (ql <= l && r <= qr)
			v[rt].cnt += c;
		else
		{
			int m = l + r >> 1;
			if (ql <= m)
				upd(ql, qr, c, l, m, rt << 1);
			if (qr > m)
				upd(ql, qr, c, m + 1, r, rt << 1 | 1);
		}
		if (v[rt].cnt)
		{
			v[rt].lbd = v[rt].rbd = 1;
			v[rt].sum = rk[r + 1] - rk[l];
			v[rt].vtl = 2;
		}
		else if (l == r)
			v[rt].sum = v[rt].vtl = v[rt].lbd = v[rt].rbd = 0;
		else
		{
			v[rt].lbd = v[rt << 1].lbd;
			v[rt].rbd = v[rt << 1 | 1].rbd;
			v[rt].sum = v[rt << 1].sum + v[rt << 1 | 1].sum;
			v[rt].vtl = v[rt << 1].vtl + v[rt << 1 | 1].vtl;
			if (v[rt << 1].rbd && v[rt << 1 | 1].lbd)
				v[rt].vtl -= 2;
		}
	}
	ll ask()
	{
		rk.init();
		sort(s.begin(), s.end());
		v.assign(rk.size() << 2, Node());
		ll ans = 0;
		for (int i = 0; i + 1 < s.size(); ++i)
		{
			ll pre = v[1].sum;
			upd(rk.ask(s[i].l), rk.ask(s[i].r) - 1, s[i].f, 0, rk.size() - 1);
			ans += v[1].vtl * (s[i + 1].h - s[i].h) + abs(v[1].sum - pre);
		}
		return ans + abs(v[1].sum);
	}
};
int main()
{
	for (int n; ~scanf("%d", &n);)
	{
		Perimeter p;
		for (int i = 0, l, b, r, t; i < n; ++i)
		{
			scanf("%d%d%d%d", &l, &b, &r, &t);
			p.add(l, b, r, t);
		}
		printf("%d\n", p.ask());
	}
}

矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结） wu-kan

Atlantis

覆盖的面积

Picture

解法一

解法二