1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <iostream>
#include <cstring>
using namespace std;
const int MAXN=1e5+2;
const int INF=0x7fffffff;
struct node_t{
int ls,rs;
int tag;
}d[MAXN<<5];
int rt,cnt,vis[MAXN];
#define MID int m=s+((t-s)>>1)
#define lson d[p].ls
#define rson d[p].rs
inline void pushdown(int p,int s,int t){
MID;
if(s!=t&&d[p].tag){
if(!lson)lson=++cnt;
if(!rson)rson=++cnt;
d[lson].tag=d[p].tag,d[rson].tag=d[p].tag;
d[p].tag=0;
}
}
void modify(int& p,int s,int t,int l,int r,int c){
if(!p)p=++cnt;
if(l<=s&&t<=r){
d[p].tag=c;
return;
}
MID;
pushdown(p,s,t);
if(l<=m)modify(lson,s,m,l,r,c);
if(r>m)modify(rson,m+1,t,l,r,c);
}
int query(int p,int s,int t,int l,int r){
if(!p)return 0;
if(d[p].tag){
if(vis[d[p].tag])return 0;
else return vis[d[p].tag]=1;
}
MID;
pushdown(p,s,t);
int sum=0;
if(l<=m)sum+=query(lson,s,m,l,r);
if(r>m)sum+=query(rson,m+1,t,l,r);
return sum;
}
int n;
void solve(){
rt=cnt=0;
memset(d,0,sizeof d);
memset(vis,0,sizeof vis);
cin>>n;
for(int i=1,l,r;i<=n;++i){
cin>>l>>r;
modify(rt,1,INF,l,r,i);
}
cout<<query(rt,1,INF,1,INF)<<'\n';
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
|