题目链接: 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; }