这个题非常有意思的地方是，我们发现区间[1,4]和[5,8]是紧挨着的，因为这个的数代表的是一段区间，原本我们对于普通的离散，
a[1]=1,a[2]=5,a[3]=6,a[4]=8;数组下标就是重新离散的位置，但是a[2]和a[3]明显不重叠，为此我们需要重新考虑离散的内容，其实不妨这样，如果区间的间隔大于1，那么我们插入一个数a[i]+1，这样就强行把a[i]和a[i+1]分开，因为
如三张海报为：1~10 1~4 6~10
离散化时 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10
第一张海报时：墙的1~4被染为1；
第二张海报时：墙的1~2被染为2，3~4仍为1；
第三张海报时：墙的3~4被染为3，1~2仍为2。
最终，第一张海报就显示被完全覆盖了，于是输出2，但实际上明显不是这样，正确输出为3。
新的离散方法为：在相差大于1的数间加一个数，例如在上面1 4 6 10中间加5（算法中实际上1，4之间，6，10之间都新增了数的）
为什么会这样呢？我们这样考虑，如果a[1]=3,a[2]=4那么他们两个是相邻的，这样其实离散后他们还是相邻的（因为1,2在题目的意义是相邻的），但是如果是a[1]=3,a[2]=5哈希后其实是(1,2) 它是相邻的(实际上3,5不相邻)，于是我们想到这样，既然我们中间有一段（没有数那一段）是我们所忽略的，我们可以新加一个数4,如
a[1]=3 a[2]=4 a[3]=5; 这样哈希后是1,2,3,我们认为3->1而5->3，(1,3)其实是不相邻的。这道题也就没什么问题了，最后区间查询+区间修改。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = ;
int sum[maxn<<];
int vis[maxn<<];
int li[maxn*];
int ri[maxn*];
int lsh[maxn<<];
void pushdown(int root){//把节点信息传给儿子节点
sum[root<<]=sum[root];//相应这个节点如果最后被修改成这个结果，那么他的儿子节点也应该修改
sum[root<<|]=sum[root];
sum[root]=-;//清空laze标记
}
int ans;
void update(int root,int L,int R,int C,int l,int r){
if (L<=l && r<=R)//如果被修改区间完全盖过当前区间
{
sum[root]=C;//更新
return;
}
if (sum[root]!=-)
pushdown(root);//如果不满足上述条件，我们需要把节点的信息更新，
int m=(l+r)>>;
if (m>=R)update(root<<,L,R,C,l,m);//信息完全在左子树
else if(L>m)update(root<<|,L,R,C,m+,r);//完全在右子树
else update(root<<,L,m,C,l,m),update(root<<|,m+,R,C,m+,r);
}
void query(int root,int l,int r){
// cout<<root<<endl;
if (sum[root]!=- && !vis[sum[root]])//如果当前节点的信息已经能包含所有的节点信息，并且这个节点的信息是第一次访问到
{
ans++;
vis[sum[root]]=;
return;
}
if (l==r)
{
return;
}
if (sum[root]!=-)
pushdown(root);//更新标记
int m=(l+r)/;
query(root<<,l,m);
query(root<<|,m+,r);
}
int main(){
int t;
int n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(sum,-,sizeof(sum));
memset(vis,,sizeof(vis));
int tot=;
for (int i=;i<n;i++)
{
scanf("%d%d",&li[i],&ri[i]);
lsh[tot++]=li[i];
lsh[tot++]=ri[i];
}
sort(lsh,lsh+tot);
int mm=unique(lsh,lsh+tot)-lsh;
int tt=mm;
for (int i=;i<tt;i++)
{
if (lsh[i]-lsh[i-]>)
lsh[mm++]=lsh[i-]+;
}
sort(lsh,lsh+mm);//排序 按照数组下标进行离散
for (int i=;i<n;i++){
int x=lower_bound(lsh,lsh+mm,li[i])-lsh;//查找左边的离散后的号码
int y=lower_bound(lsh,lsh+mm,ri[i])-lsh;//查找右边的离散后的号码
update(,x,y,i,,mm-);//更新
}
ans=;
query(,,mm-);
printf("%d\n",ans);
}
return ;
}