/*
線段樹 + 離散化
好像記得暑假做 樹狀數(shù)組的時候 做過一個離散化的題目, 當(dāng)時是用2分查詢
離散節(jié)點(diǎn)標(biāo)記的, 速度還是可以的, 不過那時對離散化也沒有什么概念, 大
概是沒怎么接觸, 今天做了這道題目的時候, 也算是明白了 離散化 的基本
意思,因?yàn)?nbsp;題目的 數(shù)據(jù)范圍很大 , 1- 10000000，直接線段樹的話, 先不說
內(nèi)存會不會爆, 這么大的范圍估計(jì)也是 TLE了.
仔細(xì)讀題, 可以看到 1<= N <= 10000, 也就是說 最多只有 10000個點(diǎn), 如果
每個點(diǎn)都不同, 那么最多也只有 20000 個數(shù)據(jù), 那么離散后的 范圍就相當(dāng)小;
離散化 的大概思路 : 比如說給你一組 數(shù)據(jù) 1 4 1000 100000， 如果直接
開線段, 顯然是浪費(fèi), 那么我們只要 進(jìn)行 映射 :
1 1
4 2
1000 3
100000 4
接下來 我們只要對 1 2 3 4 建立線段樹就行了 只需要
[1,4]的區(qū)間
*/
/*
Mail to : miyubai@gamil.com
Link : http://www.cnblogs.com/MiYu || http://www.shnenglu.com/MiYu
Author By : MiYu
Test : 1
Complier : g++ mingw32-3.4.2
Program : 2528
Doc Name : Mayor's posters
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
int T, N, x, y;
map < int, int > mp;
set <int> st;
map<int,int>::iterator beg, end;
struct segtree {
int left, right,cov;
int mid () { return (left+right)>>1; }
}seg[80010];
struct P { //節(jié)點(diǎn)數(shù)據(jù)
int left, right;
}pp[10010];
void creat ( int x, int y, int rt = 1 ) {
seg[rt].left = x;
seg[rt].right = y;
seg[rt].cov = 0;
if ( x == y ) return ;
int mid = seg[rt].mid();
creat ( x, mid, rt << 1 );
creat ( mid + 1, y, rt << 1 | 1 );
}
void insert ( int x, int y, int flag, int rt = 1 ) {
//如果線段被覆蓋, 直接標(biāo)記, 返回
if ( seg[rt].left == x && seg[rt].right == y ) {
seg[rt].cov = flag;
return;
}
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( seg[rt].cov != -1 ) {
//如果線段是被覆蓋的 , 標(biāo)記下傳, 同時自身標(biāo)記-1，表示有多個標(biāo)記
seg[LL].cov = seg[RR].cov = seg[rt].cov;
seg[rt].cov = -1;
}
//遞歸 插入
if ( y <= mid ) insert ( x, y, flag, LL );
else if ( x > mid ) insert ( x, y, flag, RR );
else {
insert ( x, mid, flag, LL );
insert ( mid + 1, y, flag, RR );
}
}
void query ( int x, int y, int rt = 1 ) {
// 線段被覆蓋 , 將覆蓋標(biāo)記 放入 set
if ( seg[rt].cov != -1 && seg[rt].left == x && seg[rt].right == y ) {
st.insert ( seg[rt].cov );
return ;
}else {//遞歸查詢
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( y <= mid ) query ( x, y, rt << 1 );
else if ( x > mid ) query ( x, y, rt << 1 | 1 );
else {
query ( x, mid, LL );
query ( mid + 1, y, RR );
}
}
}
void print () {
for ( set<int>::iterator it = st.begin(); it != st.end(); ++ it )
cout << *it << endl;
}
int main ()
{
scanf ( "%d", &T );
creat ( 1, 20010 );
while ( T -- ) {
mp.clear();
st.clear ();
scanf ( "%d", &N );
for ( int i = 1; i <= N; ++ i ) {
scanf ( "%d%d", &pp[i].left, &pp[i].right );
//map 去重
mp[pp[i].left] = 88; mp[pp[i].right] = 88;
}
beg = mp.begin(), end = mp.end();
//因?yàn)閙ap 已經(jīng)自動排序了,所以直接從 1 --> N 開始標(biāo)記, 離散化
for ( int i = 1;beg != end; ++ beg, ++ i ) {
beg->second = i;
}
//因?yàn)榫€段樹已經(jīng)建立好了, 所以沒必要每次都重建一次, 只要插入一條
//覆蓋所有區(qū)間的 底板 就行了
insert ( 1, N * 2, 0 );
for ( int i = 1; i <= N; ++ i ) {
//用離散后的標(biāo)記 插入 線段
insert ( mp[pp[i].left], mp[pp[i].right], i );
}
query ( 1, N * 2 );
//print();
int cnt = st.size();
if ( *st.begin() == 0 ) -- cnt;
printf ( "%d\n", cnt );
}
return 0;
}