二维LIS(CDQ分治)
2024-08-26 07:48:43
题目描述
给定一个长度为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
最新文章
- 快速Android开发系列网络篇之Volley
- 怎么使用jQuery
- iOS阶段学习第三天笔记(运算符)
- 编程之美----NIM游戏
- flume与Mosquitto的集成
- QComboBox 和 QSpinBox 使用方法
- JAVA语言基础——类型转换
- C#程序用Inno Setup打包,以管理员身份运行的处理方法
- 代码片段---判断一文件是不是字符设备如果是把它拷贝到 /dev目录下
- complex(x):创建一个复数
- Django关于filter和get()方法
- Photon引擎开发实战(1)——Photon 简介
- maven打一个可执行的jar包
- zoj2112
- Block formatting context
- python文件的中文处理以及个人思路
- C# 内存模型
- SQL对于 小数处理的小结
- schame定义及用处
- Chrome (开发者工具)快捷键
热门文章
- android ViewPager实现 跑马灯切换图片+多种切换动画
- difference in physical path, root path, virutal path, relative virtual path, application path and aboslute path?
- HTTP 各种特性应用(三)
- 常用sql语句及案例
- 新手教程:电信+广电(或其他运营商)双WAN设置
- 原生js模拟jquery中的addClass和removeClass方法
- 小试VS 2017 开发Python Django项目过程一
- cogs 26. 分组
- HDU4009 Transfer water 【最小树形图】
- 数据库范式小结 1NF 2NF BCNF 3NF 4NF DB normal form