#include<iostream>
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
int l[10005], r[10005], x[50025], tx;
struct node
{
int data;
int weight;
node *lch, *rch;
node(int key)
{
data = key;
weight = rand();
lch = NULL;
rch = NULL;
}
};
typedef node* pNode;
void leftRotate(pNode &rt)
{
pNode p = rt->lch;
rt->lch = p->rch;
p->rch = rt;
rt = p;
return;
}
void rightRotate(pNode &rt)
{
pNode p = rt->rch;
rt->rch = p->lch;
p->lch = rt;
rt = p;
return;
}
void removeAll(pNode &rt)
{
if(!rt)
return;
removeAll(rt->lch);
removeAll(rt->rch);
delete rt;
rt = NULL;
return;
}
void insert(const int key, pNode &rt)
{
if(!rt)
{
rt = new node(key);
return;
}
if (key < rt->data)
{
insert(key, rt->lch);
if(rt->lch->weight < rt->weight)
leftRotate(rt);
}
else
{
insert(key, rt->rch);
if(rt->rch->weight < rt->weight)
rightRotate(rt);
}
return;
}
void remove(const int key, pNode &rt)
{
if(!rt)
return;
if(rt->data == key)
{
if(!rt->lch && !rt->rch)
{
delete rt;
rt = NULL;
return;
}
if(!rt->rch)
{
leftRotate(rt);
remove(key, rt->rch);
return;
}
if(!rt->lch)
{
rightRotate(rt);
remove(key, rt->lch);
return;
}
if(rt->lch->weight < rt->rch->weight)
{
leftRotate(rt);
remove(key, rt->rch);
}
else
{
rightRotate(rt);
remove(key, rt->lch);
}
return ;
}
if(key < rt->data)
remove(key, rt->lch);
else
remove(key, rt->rch);
return;
}
bool quary(const int key, pNode &rt)
{
if(!rt)
{
insert(key, rt);
return false;
}
if(rt->data == key)
return true;
if(rt->data < key)
return quary(key, rt->rch);
else
return quary(key, rt->lch);
}
int erfen(int ll, int rr, int num)
{
while(ll <= rr)
{
int mid = (ll + rr) / 2;
if(x[mid] > num)
rr = mid - 1;
else
ll = mid + 1;
}
return rr;
}
int main()
{
int test, n, i, j, m, num;
bool boool, ff;
node *root = NULL;
scanf("%d", &test);
while(test --)
{
num = 0;
scanf("%d", &n);
tx = 0;
for(i = 0; i < n; i ++)
{
scanf("%d%d", &l[i], &r[i]);
x[tx ++] = l[i];
x[tx ++] = r[i];
}
sort(x, x + tx);
m = 1;
for(i = 1; i < tx; i ++)
{
if(x[i] != x[i - 1])
x[m ++] = x[i];
}
for(i = m - 1; i > 0; i --)
{
if(x[i] != x[i - 1] + 1)
x[m ++] = x[i] - 1;
}
sort(x, x + m);
//for(i = 0; i < m; i ++)
//insert(i, root);
for(i = n - 1; i >= 0; i --)
{
int a0 = l[i], b0 = r[i], a1, b1;
a1 = erfen(0, m, a0);
b1 = erfen(0, m, b0);
ff = 0;
for(j = a1; j <= b1; j ++)
{
boool = quary(j, root);
if(boool == 0)
{
ff = 1;
}
}
if(ff == 1)
num ++;
}
removeAll(root);
printf("%d\n", num);
}
system("pause");
return 0;
}
评论0