题意 贴海报 最后可以看到多少海报

思路 :离散化大区间  其中[1,4] [5,6]不能离散化成[1,2] [2,3]因为这样破坏了他们的非相邻关系 每次离散化区间 [x,y]时  把y+1点也加入就行了

注:参考了上海全能王csl的博客!

 #include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
#define X first
#define Y second
const int maxn=+;
pair<int,int>a[maxn*];
vector<int>v;
struct Node{
int l,r;
int col;
int lazy;
void update(int x){
col=x;
lazy=x;
}
}tree[maxn*];
bool vis[maxn*];
/*void push_up(int x){
if(tree[x<<1].col!=tree[x<<1|1].col||tree[x<<1].col==-1||tree[x<<1|1].col==-1)tree[x].col=-1;
}*/ void build(int x,int l,int r){
tree[x].l=l,tree[x].r=r;
tree[x].col=-;
if(l==r){
return ;
}
else {
int mid=l+r>>;
build(x<<,l,mid);
build(x<<|,mid+,r);
}
} void push_down(int x){
if(tree[x].col==-)return;
tree[x<<].col=tree[x<<|].col=tree[x].col;
tree[x].col=-;
}
void update(int x,int l,int r,int val){
int L=tree[x].l,R=tree[x].r;
if(l<=L&&R<=r){
tree[x].col=val;
return ;
}
else {
push_down(x);
int mid=(L+R)>>;
if(l<=mid)update(x<<,l,r,val);
if(mid<r)update(x<<|,l,r,val);
// pudh_up(x);单点查询不需要合并
}
}
long long query(int x,int a){
int L=tree[x].l,R=tree[x].r;
if(L==R)return tree[x].col;
push_down(x);
int mid=L+R>>;
if(mid>=a)query(x<<,a);
else if(mid<a)query(x<<|,a);
} int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
memset(vis,,sizeof(vis));
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d",&a[i].X,&a[i].Y);
v.push_back(a[i].X);
v.push_back(a[i].Y);
v.push_back(a[i].Y+);
}
sort(v.begin(),v.end());
int num=unique(v.begin(),v.end())-v.begin();
for(int i=;i<n;i++){
a[i].X = lower_bound(v.begin(), v.begin() + num, a[i].X) - v.begin() + ;
a[i].Y = lower_bound(v.begin(), v.begin() + num, a[i].Y) - v.begin() + ;
}
build(,,num);
for(int i=;i<n;i++){
update(,a[i].X,a[i].Y,i+);
}
int ans=;
for(int i=;i<=num;i++){
int col=query(,i);
// cout<<col<<endl;
if(col!=-&&vis[col]==){
vis[col]=;
ans++;
}
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. ES搜索引擎-简单入门
  2. Java中的内部类(成员内部类、静态内部类、局部内部类、匿名内部类)
  3. Nova 操作汇总(限 libvirt 虚机) [Nova Operations Summary]
  4. Java原来如此-比较器(Comparable、Comparator)
  5. C#线程状态简析
  6. 玩转无线电 -- 温哥华天车 RFID 票务系统
  7. leetcode007. Reverse Integer
  8. PHP全栈工程师学习大纲
  9. cocos2d-x学习笔记
  10. 用eval 动态编译代码
  11. jquery.validate 一些技巧
  12. 基于visual Studio2013解决面试题之0506取和为m的可能组合
  13. winform实现动态按钮
  14. PHP开发高可用高安全App后端
  15. 我是怎样使用javassist将代码注入到帝国OL并进行调试的
  16. PLSQL复合触发器
  17. [UE4]UMG和关卡坐标变换、旋转小地图
  18. Oracle_高级功能(9) 性能优化
  19. UVa 11077 Find the Permutations (计数DP)
  20. Java中函数的重载和重写

热门文章

  1. ASP.Net Core 运行错误 Http Error 502.5 解决办法
  2. java 浅克隆 深克隆
  3. Graph Without Long Directed Paths CodeForces - 1144F (dfs染色)
  4. Django admin参数配置
  5. windows中在vs code终端使用bash
  6. MySQL中关于数据类型指定宽度之后的情况
  7. spring datasource jdbc 密码 加解密
  8. 六、es6 map
  9. Spring boot+ logback环境下,日志存放路径未定义的问题
  10. servlet中将值以json格式传入