由于坐标可能很大,此时需要离散化,将值转化为对应的坐标。

#include<stdio.h>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 200010
int mark[maxn*],sum[maxn*],ans;
struct Node
{
int x;
int y;
}node[maxn];
int num[maxn*];
void pushup(int rt)
{
if(sum[rt<<]&&sum[rt<<|])
sum[rt]=;
else sum[rt]=;
}
void build(int l,int r,int rt)
{ if(l==r)
{
sum[rt]=;
return ;
}
int m=(l+r)/;
build(lson);
build(rson);
pushup(rt);
} void updata(int L,int R,int l,int r,int rt,int c)
{
if(sum[rt]) return ;
if(l>=L&&R>=r)
{
sum[rt]=;
if(!mark[c])
{
mark[c]=;
ans++;
return ;
}
return ;
}
int m=(l+r)/;
if(m>=L)
updata(L,R,lson,c);
if(R>m)
updata(L,R,rson,c);
pushup(rt);
}
int find(int val,int x,int y)
{
int l=x;
int r=y;
int m;
while(l<=r)
{
m=(l+r)/;
if(num[m]==val)
return m;
else if(num[m]>val)
r=m-;
else l=m+;
}
return -;
}
int main()
{
int i,t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int m=;
for(i=;i<n;i++)
{
scanf("%d%d",&node[i].x,&node[i].y);
num[m++]=node[i].x;
num[m++]=node[i].y;
}
sort(num+,num+m);
int k=;
//去重复
for(i=;i<m;i++)
{
if(num[i]!=num[i-])
num[k++]=num[i];
}
//防止相邻的出现问题
for(i=k-;i>;i--)
{
if(num[i]!=num[i-]+)
num[k++]=num[i-]+;
}
memset(mark,,sizeof(mark));
sort(num+,num+k);
build(,k-,);
ans=;
for(i=n-;i>=;i--)//倒着贴
{
int ll=find(node[i].x,,k-);
int rr=find(node[i].y,,k-);
updata(ll,rr,,k-,,i+);
}
printf("%d\n",ans);
}
}

最新文章

  1. Struts2中的Ognl
  2. [转]Flex 布局教程:语法篇
  3. pull解析和sax解析的差别
  4. Mapper映射语句高阶应用——ResultMap
  5. STM32 水晶不摇
  6. MyBatis延迟加载和缓存
  7. Java IO--字符流--BufferedReader和BufferedWriter
  8. Springboot 系列(十)使用 Spring data jpa 访问数据库
  9. 我的第一个python web开发框架(26)——定制ORM(二)
  10. C++设计模式——外观模式
  11. mysql Navicat客户端
  12. Linux下键盘值 对应input_evnet的code值。
  13. Dubbo--基于Zookeeper服务与Spring集成
  14. Shell 中字符串变量的赋值注意点
  15. [svc]linux的ip命令操作接口和路由表
  16. [Linux] 修改系统默认编码
  17. Python.错误解决:scrapy 没有crawl 命令
  18. python 自然语言处理库https://www.nltk.org/nltk_data/
  19. 021.15 IO流 其他流
  20. key Value

热门文章

  1. 车脸检测 Adaboost 检测过程
  2. PPP(点对点协议(Point to Point Protocol)
  3. Volley(三)—— ImageRequest &amp; Request简介
  4. (转) C#多线程赛跑实例
  5. Spring之AOP
  6. 【转】【C#】ColorMatrix
  7. 推荐一款开源的C#TCP通讯框架
  8. 补鞋匠---Cobbler 服务器自动搭建
  9. Linux 网络编程一(TCP/IP协议)
  10. C语言 百炼成钢17