离散化 去掉重复点 排序 二分查找
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 40005
using namespace std;
int pp[maxn][2];
int x[2*maxn],f[2*maxn];
int d[2*maxn];
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
memset(f, 0 ,sizeof(0));
int n;
scanf("%d",&n);
for(int i= 0; i < n; i++)
{
scanf("%d%d",&pp[i][0],&pp[i][1]);
x[i] = pp[i][0];
x[2*i+1] = pp[i][1];
}
sort(x, x+2*n);
d[0] = x[0];
int cc = 1;
for(int i = 1; i < 2*n; i++)
{
if(x[i] != d[cc-1])
{
d[cc++] = x[i];
}
}
for(int i = 0; i < n; i++)
{
int ri = lower_bound(d, d+cc, pp[i][0])-d;
int le = lower_bound(d, d+cc, pp[i][1])-d;
for(int j = ri; j <= le; j++)
f[j] = i;
}
sort(f, f+cc);
int ans = 1;
for(int i = 1; i < cc; i++)
{
if(f[i] != f[i-1])
ans++;
}
printf("%d\n",ans);
}
return 0;
}