＃795 Div.2 E. Number of Groups set *

link

The question

Line segments with two colors , In line segments with different colors , There are connecting edges between segments with intersecting parts . Find the number of connected blocks of a graph .
The number of line segments shall not exceed $10^5$ .

Ideas

Divide each line segment into outgoing point and incoming point , And sort from small to large , Traverse this one by one $2n$ A little bit , The entry point is equivalent to adding this line segment , The point is deleted . Maintain... Separately through set consolidation $1$ and $0$ Line segment of .

because $n\le 10^5$, So we can't $O(n^2)$ Violence is everywhere , Consider how to optimize .

Because we sort the coordinates from small to large , We Just keep the segment with the largest right endpoint among all segments , Other line segments can be deleted ( Because as long as it can merge with the segment with the largest right endpoint , It must be possible to merge the points previously merged with the right endpoint with other deleted segments ). In this way, the number of times to divide and check the collection becomes $O(n)$, The total complexity is $O(n\log n)$.

Code

int n;
int fa[maxn];
int find(int x) {
    
	if(fa[x] == x) return x;
	return fa[x] = find(x);
}
void merge(int x, int y) {
    
	int fx = find(x);
	int fy = find(y);
	if(fx == fy) return;
	fa[fy] = fx;
	find(fy);
}
struct Node {
    
	int c, l, r;
}a[maxn];
void solve() {
    
    cin >> n;
    for(int i = 1; i <= n; i++) fa[i] = i;
    vector<pii> op;
    for(int i = 1; i <= n; i++) {
    
    	cin >> a[i].c >> a[i].l >> a[i].r;
    	op.pb({
    a[i].l, -i});
    	op.pb({
    a[i].r, i});
    }
    sort(op.begin(), op.end());
    set<pii> s[2];
    for(auto [pos, id] : op) {
    
    	if(id < 0) {
    
    		id = -id;
    		s[a[id].c].insert({
    a[id].r, id});
    		int t = a[id].c ^ 1;
    		while(s[t].size() > 1) {
    
    			merge(id, s[t].begin()->second);
    			s[t].erase(s[t].begin());
    		}
    		if(!s[t].empty()) {
    
    			merge(id, s[t].begin()->second);
    		}
    	}
    	else {
    
    		s[a[id].c].erase({
    a[id].r, id});
    	}
    }
    int res = 0;
    for(int i = 1; i <= n; i++) {
    
	    res += (find(i) == i);
	}
	cout << res << endl;
}