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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include <queue>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <set>
#define lson i<<1
#define rson i<<1|1
using namespace std;
const int manx = 20000 + 5;
const int MANX =1e7+10;
typedef long long ll;
ll posi1[manx << 1], posi2[manx << 1];
set<ll> st;
ll id[MANX ];
ll vis[manx<<1];
struct tree
{
ll l,r;
int rang;
}tree[manx<<2];
void pushDown(ll i)
{
if(tree[i].rang)
{
tree[lson].rang=tree[rson].rang=tree[i].rang;
tree[i].rang=0;
}
return ;
}
void build_tree(ll i,ll l,ll r)
{
//cout<<i<<endl;
tree[i].l=l;
tree[i].r=r;
tree[i].rang=0;
if(l==r)
return ;
int mid=l+r>>1;
build_tree(lson,l,mid);
build_tree(rson,mid+1,r);
}
void change(ll i,ll l,ll r,ll c)
{
//cout<<c<<endl;
if(tree[i].l>=l&&tree[i].r<=r)
{
tree[i].rang=c;
return ;
}
pushDown(i);
int mid=tree[i].l+tree[i].r>>1;
if(l<=mid ) change(lson,l,r,c);
if(r>mid) change(rson,l,r,c);
}
ll query(ll i)
{
//cout<<tree[i].rang<<' '<<tree[i].l<<' '<<tree[i].r<<endl;
if(tree[i].rang)
{
ll x=tree[i].rang;
if(!vis[x])
{
vis[x]=1;
return 1;
}
return 0;
}
pushDown(i);
if(tree[i].l==tree[i].r)
return 0;
return query(lson)+query(rson);
}
int main()
{
int t;
scanf("%d", &t);
while(t--){
ll q;
memset(vis,0,sizeof vis);
st.clear();
scanf("%lld", &q);
for (int i = 1; i <=q;i++)
{
scanf("%lld%lld", &posi1[i], &posi2[i]);
st.insert(posi1[i]);
st.insert(posi2[i]);
}
ll cnt=1;
for(set<ll>::iterator it=st.begin();it!=st.end();it++)
{
id[*it]=cnt++;
}
build_tree(1,1,cnt);
for(int i=1;i<=q;i++)
{
change(1,id[posi1[i]],id[posi2[i]],i);
}
printf("%lldn",query(1));
}
}
|
近期评论