题目描述

给定一个长度为N的序列S,S的每个元素pi是一个二元组(xi,yi),定义pi<pj当且仅当xi<xj并且yi<yj,求S的最长上升子序列长度

输入格式

第一行一个N,表示一共有N个元素

接下来有N行,每行包含两个正整数xi,yi

输出格式

输出一行一个整数,代表序列S的最长上升子序列的长度

一道很好的模板题,比较入门吧

CDQ分治+线段树/树状数组维护最大值就好了

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct nasm{
int x,y,z;
}a[];
int f[];
int tr[];
int tmp[];
int n;
bool cmp(nasm g,nasm u)
{
return g.y<u.y;
}
bool cmq(nasm g,nasm u)
{
return g.x<u.x;
}
void updt(int pi,int v,int l,int r,int spc)
{
if(l==r)
{
tr[spc]=v==?v:max(v,tr[spc]);
return ;
}
int m=(l+r)>>;
if(pi<=m)
updt(pi,v,l,m,spc<<);
else
updt(pi,v,m+,r,spc<<|);
tr[spc]=max(tr[spc<<],tr[spc<<|]);
}
int ask(int ll,int rr,int l,int r,int spc)
{
if(ll>rr)return ;
if(l>=ll&&r<=rr)return tr[spc];
int m=(l+r)>>;
if(m>=rr)return ask(ll,rr,l,m,spc<<);
if(m<ll)return ask(ll,rr,m+,r,spc<<|);
return max(ask(ll,rr,l,m,spc<<),ask(ll,rr,m+,r,spc<<|));
}
void wrk(int l,int r)
{
int mid=(l+r)>>;
sort(a+l,a+mid+,cmp);
sort(a+mid+,a+r+,cmp);
for(int i=l,j=mid+;j<=r;j++)
{
for(;a[i].y<a[j].y&&i<=mid;i++)
updt(a[i].z,f[a[i].x],,n,);
f[a[j].x]=max(f[a[j].x],ask(,a[j].z-,,n,)+);
}
for(int i=l;i<=mid;i++)updt(a[i].z,,,n,);
sort(a+mid+,a+r+,cmq);
}
void cdq(int l,int r)
{
if(l==r)
return ;
int mid=(l+r)>>;
cdq(l,mid);
wrk(l,r);
cdq(mid+,r); }
int erf(int l,int r,int aim)
{
if(l==r)return l;
int m=(l+r)>>;
if(aim<=tmp[m])
return erf(l,m,aim);
return erf(m+,r,aim);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i].y,&a[i].z);
f[i]=;
a[i].x=i;
tmp[i]=a[i].z;
}
sort(tmp+,tmp+n+);
for(int i=;i<=n;i++)
a[i].z=erf(,n,a[i].z);
cdq(,n);
int ans=;
for(int i=;i<=n;i++)
ans=max(ans,f[i]);
printf("%d\n",ans);
return ;
}

二维LIS

最新文章

  1. 快速Android开发系列网络篇之Volley
  2. 怎么使用jQuery
  3. iOS阶段学习第三天笔记(运算符)
  4. 编程之美----NIM游戏
  5. flume与Mosquitto的集成
  6. QComboBox 和 QSpinBox 使用方法
  7. JAVA语言基础——类型转换
  8. C#程序用Inno Setup打包,以管理员身份运行的处理方法
  9. 代码片段---判断一文件是不是字符设备如果是把它拷贝到 /dev目录下
  10. complex(x):创建一个复数
  11. Django关于filter和get()方法
  12. Photon引擎开发实战(1)——Photon 简介
  13. maven打一个可执行的jar包
  14. zoj2112
  15. Block formatting context
  16. python文件的中文处理以及个人思路
  17. C# 内存模型
  18. SQL对于 小数处理的小结
  19. schame定义及用处
  20. Chrome (开发者工具)快捷键

热门文章

  1. android ViewPager实现 跑马灯切换图片+多种切换动画
  2. difference in physical path, root path, virutal path, relative virtual path, application path and aboslute path?
  3. HTTP 各种特性应用(三)
  4. 常用sql语句及案例
  5. 新手教程:电信+广电(或其他运营商)双WAN设置
  6. 原生js模拟jquery中的addClass和removeClass方法
  7. 小试VS 2017 开发Python Django项目过程一
  8. cogs 26. 分组
  9. HDU4009 Transfer water 【最小树形图】
  10. 数据库范式小结 1NF 2NF BCNF 3NF 4NF DB normal form