思路:分治思想。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
const int INF=0x3f3f3f3f;
const int N=1e4+;
int st[N],ed[N];
bool vis[N]={false};
int ans;
void dfs(int l,int r,int x)
{
if(x==)return ;
if(l<=ed[x]&&r>=st[x])
{
if(!vis[x])
{
ans++;
vis[x]=true;
}
if(l<st[x])dfs(l,st[x]-,x-);
if(r>ed[x])dfs(ed[x]+,r,x-);
}
else dfs(l,r,x-);
}
int main()
{
int c,n;
scanf("%d",&c);
while(c--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&st[i],&ed[i]);
}
ans=;
memset(vis,false,sizeof(vis));
dfs(,,n);
printf("%d\n",ans);
}
return ;
}