Lutece 2145 人在地上走,锅从天上来

题目链接: https://acm.uestc.edu.cn/problem/ren-zai-di-shang-zou-guo-cong-tian-shang-lai/description

题目大意:每次覆盖一个区间,求有多少个独立的区间

分析:

这道题的核心思想就是将相等与相交联系起来。

用堆来维护每一条线段,方便快速查询。查找到相等,即与线段相交的时候,就取出来合并。

堆中元素的个数就是答案。

需要注意的是,set使用 A < B || B < A 这个表达式的值来判断是否相等,这个表达式为假则相等。

代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int l, r;
	bool operator < (const node &a) const
	{
		if (l <= a.r && a.r <= r)
			return false;
		if (l <= a.l && a.l <= r)
			return false;
		if (a.l <= l && l <= a.r)
			return false;
		if (a.l <= r && r <= a.r)
			return false;
		return r < a.r;
	}
};
set<node> s;
node merge(node a, node b)
{
	node qwe;
	qwe.l = min(a.l, b.l);
	qwe.r = max(a.r, b.r);
	return qwe;
}
int main()
{
	ios::sync_with_stdio(false);
	int n,q,w;
	node linshi;
	set<node>::iterator it;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> q >> w;
		linshi.l = q; linshi.r = w;
		it=s.find(linshi);
		while (it != s.end())
		{
			linshi = merge(linshi, *it);
			s.erase(it);
			it = s.find(linshi);
		}
		s.insert(linshi);
		cout << s.size() << " ";
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注