由于楼上大佬太强了，题解看了很久才看懂，~甚至研究了代码~，所以又写了一篇题解，希望能帮助大家理解。

题目意思

现有 $n$ 个操作，每次操作给定一个区间，求此时连通块个数。

对于两个区间 $i$ 和 $j$，如果它们互相包含它们就是一组连通块，或者通过一系列的区间构成连通块。

题目思路

考虑一个新区间 $i$，与一个连通块 $j$ 合并所需的条件。

首先容易想到的，如果连通块可以包含该区间，即满足图中条件。

图中红色区间为连通块，黑色为新加入的区间。

图中 $l_{min}$ 和 $r_{max}$，为连通块中的最小左端点和最大右端点。

显然上述条件是满足的。即 $l_{min} \le L$ 且 $R \le r_{min}$。

但是不仅如此，还有两种情况也可行。 如图。

图中红色的两个区间表示一个连通块，黑色是新加入的区间，则此时新加入的区间也可以加入连通块。

即有两种情况。

• 新加入区间的左端点在连通块的内部，右端点在连通块外部。
• 新加入区间的左端点在连通块的外部，右端点在连通块内部。

两种情况差不多，我就只考虑第二种了，第一种自己考虑吧，~其实是笔者懒得打~。

首先考虑左端点在外部，即 $L \le l_{min}$。

考虑此时新区间和连通块合并的条件。

对于左端点的条件显然已经满足，考虑右端点。

如果能合并，那么新区间的右端点应该大于连通块中任意区间的右端点，即最小的右端点。

即满足 $r_{min} \le R$。

总的来说，这种情况需满足，$L \le l_{min}$ 且 $r_{min} \le R$。 另一种情况同样的，要满足 $r_{max} \le R$ 且 $L \le l_{max}$。

也就是说满足以下条件，我们就称新加入的区间能加入到当前连通块中。

• $l_{min} \le L$ 且 $R \le r_{min}$。
• $L \le l_{min}$ 且 $r_{min} \le R$。
• $r_{max} \le R$ 且 $L \le l_{max}$。

也就是说，对于每一个连通块，我们都需要记连通块的所有区间中最大最小的左右端点。

但问题还没解决。

我们怎么做到快速查找每一个连通块是个问题。

考虑连通块和区间合并的性质。

对于两个连通块 $a$ 和 $b$ 还有一个新区间来说，如果 $a_{l_{min}} \le b_{l_{min}}$，也就是如图，此时新区间在连通块左边。

我们假设连通块 $a$ 不可以与新区间合并，那么因为区间在连通块左侧所以满足 $a_{r_{min}} > R$，则 $a$ 的最小右端点必在 $R$ 的右侧。

那么如果在这个前提下，$b$ 可以与新区间合并那么必满足 $b_{r_{min}} \le R$，故 $a_{r_{min}} > b_{r_{min}}$，那如果这样的话， $a$ 和 $b$ 不就是一个连通块了吗。因为 $a_{l_{min}} \le b_{l_{min}}$ 且 $b_{r_{min}} \le a_{r_{min}}$，满足上述条例。

这不就是一个很好用的性质了吗。

也就是说，将连通块按照最小左端点排序，那么当遇到一个无法和区间合并的连通块，那么在它后面的连通块也不要用考虑了。

对于另一种情况，即区间在连通块左侧，其实差不多，~我懒得写了~，告诉你们性质自己推。

性质，将连通块按照最小左端点从小到大排列。这时我们从左端点最大的，且满足在区间左端的连通块开始，依次往下，当遇到第一个不满足条件的连通块，退出即可。

好了，那你知道这俩性质你咋弄呢。

首先第一个问题，你怎么快速找到已有连通块中，满足 $L \le l_{min}$，这其实比较简单，可以用 $\ set$ 维护。

由于 $\ set$ 可以用 $\log(n)$ 的时间快速排序，我们就用它排序左端点，然后用二分查找即可。

接下来的事情就好办的多，直接暴力往上跳，往下跳，遇到不符合条件的退出即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
	int lm,lx,rm,rx;
};
bool operator <(node aa,node bb)
{
	return aa.lm<bb.lm;
}
bool pd(node a1,int L,int R)//三个条件判断是否能合并 
{
	if(a1.lm<=L&&R<=a1.rx||L<=a1.lm&&R>=a1.rm||R>=a1.rx&&L<=a1.lx) return true;
	return false;
}
void turn_into(node &a,node b)//记得更新，因为你要存lmax,rmax,lmin,rmin,新加入一个区间肯定是要更新的 
{
	a.lm=min(a.lm,b.lm);
	a.lx=max(a.lx,b.lx);
	a.rm=min(a.rm,b.rm);
	a.rx=max(a.rx,b.rx);
}
set<node> s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int ll,rr;
		cin>>ll>>rr;
		node temp,cp;
		temp.lm=temp.lx=ll;
		temp.rm=temp.rx=rr;
		cp=temp;
		auto p=s.lower_bound(temp);
		while(p!=s.end())
		{
			if(!pd(*p,ll,rr)) break;
			turn_into(temp,*p);
			p++;
			s.erase(prev(p));//prev 指当前位置的上一个 
		}
		p=s.lower_bound(cp);
		while(p!=s.begin())
		{
			if(!pd(*prev(p),ll,rr)) break;
			turn_into(temp,*prev(p));
			s.erase(prev(p));
		}	
		s.insert(temp);
		cout<<s.size()<<"\n";
	}	
	return 0;
}