http://poj.org/problem?id=2528
这个题有个细节，整个区间的长度为10000000，而n最大只有1000，所以我们要进行离散化。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 10010
using namespace std; bool tab[maxn];
int l[maxn],r[maxn],x[maxn*],num[maxn*],tree[maxn*];
int c,n; int binary_search1(int sum)
{
int l=,r=*n;
while(l<=r)
{
int mid=(l+r)/;
if(x[mid]<=sum)
l=mid+;
else
r=mid-;
}
return num[r];
} void update(int i)
{
if(!tree[i])
return ;
tree[i+i]=tree[i+i+]=tree[i];
tree[i]=;
}
void change(int tl,int tr,int l,int r,int i,int co)
{
if(tl>r||tr<l) return ;
if(tl<=l&&r<=tr)
{
tree[i]=co;
return ;
}
update(i);
int mid=(l+r)/;
change(tl,tr,l,mid,i+i,co);
change(tl,tr,mid+,r,i+i+,co);
}
int require(int l,int r,int i)
{
int mid=(l+r)/;
if(tree[i])
{
if(!tab[tree[i]])
{
tab[tree[i]]=;
return ;
}
return ;
}
if(l==r)
return ;
return require(l,mid,i+i)+require(mid+,r,i+i+);
}
void init()
{
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d%d",l+i,r+i);
x[i*-]=l[i];x[i*-]=r[i];x[i*]=(l[i]+r[i])/;
}
sort(x+,x+*n+);
memset(num,,sizeof(num));
for(int i=; i<=*n; i++)
{
num[i]=num[i-];
if(x[i]!=x[i-]) num[i]++;
}
for(int i=; i<=n; i++)
{
l[i]=binary_search1(l[i]);
r[i]=binary_search1(r[i]);
}
} void solve()
{
memset(tree,,sizeof(tree));
for(int i=; i<=n; i++)
{
change(l[i],r[i],,*n,,i);
}
memset(tab,,sizeof(tab));
int ans=require(,*n,);
printf("%d\n",ans);
} int main()
{
scanf("%d",&c);
while(c--)
{
init();
solve();
}
return ;
}