【线段树】Mayor's posters

1
3
1 3
6 10
1 10

//正确输出：3
//错误输出：2
//问题原因：离散化成了[1,2] [3,4] [1,4]，这样确实只剩下2了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;
	return x*f;
}
const int MAXN=200001;
const int INF=999999;
int N,M;
int T;
int A[MAXN*2],a[MAXN*2],b[MAXN*2];
int tr[MAXN*8+100];
int cnt,tmp3;
bool flag[MAXN*8+100];
bool Hash[MAXN*8+100];
int tmp;

void tage_lazy(int rt,int l,int r){
	if(flag[rt]){
		flag[rt*2]=flag[rt*2+1]=true;
		tr[rt*2]=tr[rt*2+1]=tr[rt];
		flag[rt]=false;
	}
	return ;
}
void add(int l,int r,int rt,int L,int R){
	if(L<=l&&R>=r){
		tr[rt]=cnt;
		flag[rt]=true;
		return ;
	}
	tage_lazy(rt,l,r);
	int mid=(l+r)>>1;
	if(mid<R) add(mid+1,r,rt*2+1,L,R);
	if(mid>=L) add(l,mid,rt*2,L,R);
	return ;
}
int Que(int l,int r,int rt,int L,int R){
	if(flag[rt]){
		if(!Hash[tr[rt]]){
			Hash[tr[rt]]=true;
			return 1;
		}
		else return 0;
	}
	if(l==r) return 0;
	int mid=(l+r)>>1;
	return Que(l,mid,rt*2,L,R)+Que(mid+1,r,rt*2+1,L,R);
}

int main(){
    T=read();
    while(T--){
	    memset(tr,0,sizeof(tr));
	    memset(flag,false,sizeof(flag));
	    memset(Hash,false,sizeof(Hash));
    	N=read();tmp=tmp3=0;
    	for(int i=1;i<=N;i++){
    		++tmp;A[tmp]=a[tmp]=read();
    		++tmp;A[tmp]=a[tmp]=read();
		}
		sort(a+1,a+tmp+1);
		int tmp2=0;int treef=tmp;
		for(int i=1;i<=tmp;i++) 
		    if(a[i]==a[i-1]) treef--;
		    else b[++tmp3]=a[i];
		int k=tmp3;
		for(int i=1;i<=k;i++)
		    if(b[i]>b[i-1]+1) b[++tmp3]=b[i-1]+1;
		sort(b+1,b+tmp3+1);
		treef=tmp3;
		for(int i=1;i<=N;i++){
			++cnt;
			int l=lower_bound(b+1,b+tmp3+1,A[tmp2+1])-b;
			int r=lower_bound(b+1,b+tmp3+1,A[tmp2+2])-b;
			add(1,treef,1,l,r);
			tmp2+=2;
		}
		printf("%d\n",Que(1,treef,1,1,treef)); 
	}
}