luogu

acwing

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

const int maxn=10005;
int T;
int b[maxn*2],n,len=0;
int ans=0;
map<int,int> S;
map<int,int> cnt;
int now=0;
struct opt
{
	int l,r;
}op[maxn];

struct node
{
	int l,r;
	int val,tag;
}tr[maxn];
void print(node x)
{
	cout<<x.l<<" "<<x.r<<" "<<x.val<<" "<<x.tag<<endl;
}

int ls(int p)
{
	return p<<1;
}
int rs(int p)
{
	return p<<1|1;
}
void pushup(int p)
{
	if(tr[ls(p)].val==tr[rs(p)].val) tr[p].val=tr[ls(p)].val;
}
void pushdown(int p)
{
	int tag=tr[p].tag;
	if(tr[p].tag)
	{
		tr[ls(p)].val=tag;
		tr[rs(p)].val=tag;
		tr[ls(p)].tag=tag;
		tr[rs(p)].tag=tag;
		tr[p].tag=0;
	}
}
void build(int p,int l,int r)
{
	tr[p].l=l,tr[p].r=r;
	if(l==r)
	{
		tr[p].val=0;
		return;
	}
	int mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}
void update(int p,int l,int r,int x)
{
	
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		tr[p].val=x;
		tr[p].tag=x;
		return;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)/2;
	if(mid>=l) update(ls(p),l,r,x);
	if(mid<r) update(rs(p),l,r,x);
	pushup(p);
}
void query(int p,int x)
{
//	cout<<tr[p].l<<" "<<tr[p].r<<endl;
	if(tr[p].l==x&&tr[p].r==x)
	{
		if(tr[p].val!=-1&&tr[p].val!=0) cnt[tr[p].val]=1;
		return;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)/2;
	if(mid>=x) query(ls(p),x);
	else  query(rs(p),x);
}

void init()
{
	memset(b,0,sizeof b);
	len=0;
	S.clear();
	memset(tr,0,sizeof tr);
	memset(op,0,sizeof op);
	n=0;
	cnt.clear();
}

int main()
{
	#ifndef ONLINE_JUDGE
// 	freopen("in.txt","r",stdin);
 	#endif
 	cin>>T;
 	while(T--)
 	{
	 	init();
	  	scanf("%d",&n);
	  	for(int i=1;i<=n;i++)
	  	{
	 	 	scanf("%d%d",&op[i].l,&op[i].r);
	 	 	b[++len]=op[i].l,b[++len]=op[i].r;
	 	}
	 	sort(b+1,b+len+1);
	 	len=unique(b+1,b+len+1)-b-1;
	 //		for(int i=1;i<=len;i++) cout<<b[i]<<" ";cout<<endl;
	 	S[b[1]]=1,now=1;
	 	for(int i=2;i<=len;i++)
	 	{
	 		if(b[i-1]==b[i]-1)
	 		{
	 			S[b[i]]=++now;
	 		}
	 		else
	 		{
	 			now+=2;
	 			S[b[i]]=now;
	 		}
	 	}
	 	build(1,1,now);
	 	for(int i=1;i<=n;i++)
	 	{
	 		int x=S[op[i].l],y=S[op[i].r];
	 		update(1,x,y,i);
	 	}
	 	for(int i=1;i<=now;i++)
	 	{
	 		query(1,i);
	 	}
	 	cout<<cnt.size()<<endl;
	}
	
	return 0;
}
/*
1000 10
89 100
51 52
77 90
20 42
48 53
3 33
52 78
91 97
49 64
2 4
*/