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

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

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());
	}
}