BZOJ2225: [Spoj 2371]Another Longest Increasing CDQ分治,3维LIS
2024-08-30 16:45:20
Code:
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 200000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,ans[maxn],hh[maxn];
inline void getmax(int &a,int b){ if(b>a)a=b; }
struct Node{
int x,y,z,org;
}node[maxn];
int cmpx(Node a,Node b)
{
if(a.x==b.x&&a.y==b.y) return a.z<b.z;
else if(a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
int cmpy(Node a,Node b){
if(a.y==b.y) return a.z<b.z;
else return a.y<b.y;
}
struct BIT{
int C[maxn];
int lowbit(int t) { return t&(-t);}
void update(int p,int x){ while(p<maxn) getmax(C[p],x),p+=lowbit(p); }
int query(int p){
if(p<=0) return 0;
int ss=0;
while(p>0) getmax(ss,C[p]),p-=lowbit(p);
return ss;
}
void del(int p){ while(p<maxn)C[p]=0,p+=lowbit(p); }
}tree;
void solve(int l,int r){
if(l>=r) return;
int mid=(l+r)>>1,tl=l,tr=mid+1;
solve(l,mid);
sort(node+l,node+mid+1,cmpy),sort(node+mid+1,node+r+1,cmpy); while(tl<=mid&&tr<=r) {
if(node[tl].y<node[tr].y) {
tree.update(node[tl].z,ans[node[tl].org]);
++tl;
}
else {
getmax(ans[node[tr].org],tree.query(node[tr].z-1)+1);
++tr;
}
}
for(int i=tr;i<=r;++i) getmax(ans[node[i].org],tree.query(node[i].z-1)+1);
for(int i=l;i<=mid;++i) tree.del(node[i].z);
sort(node+mid+1,node+1+r,cmpx),solve(mid+1,r);
} int main(){
//setIO("input");
scanf("%d",&n);
for(int i=1;i<=n;++i) node[i].x=node[i].org=i,scanf("%d%d",&node[i].y,&node[i].z),hh[i]=node[i].z;
sort(hh+1,hh+1+n);
for(int i=1;i<=n;++i) node[i].z=lower_bound(hh+1,hh+1+n,node[i].z)-hh;
for(int i=1;i<=n;++i) ans[i]=1;
sort(node+1,node+1+n,cmpx);
solve(1,n);
int h=0;
for(int i=1;i<=n;++i) getmax(h,ans[i]);
printf("%d",h);
return 0;
}
最新文章
- Oracle EBS进化史
- spark on centos6.5 安装
- OpenGL问题拾遗
- ServiceStack.OrmLite 笔记8 -还是有用的姿势
- springmvc 注解 RequestParam/RequestHeader/CookieValue
- 洛谷P1206 [USACO1.2]回文平方数 Palindromic Squares
- PHP 对象和数组互相转换
- 【BZOJ】【1770】【Usaco2009 Nov】lights 灯
- TDirectory.GetParent获取指定目录的父目录
- Windows Azure入门教学系列 (五):使用Queue Storage
- 纸飞机AE小教程
- python进程和线程(四)
- C++ WString与String互相转换
- Linux LAMP架构搭建
- Mybatis 接口传入多个参数 xml怎么接收
- 从996到ICU——我们终将被自我厌恶
- 20172319 2018.04.11-16 《Java程序设计教程》 第6周学习总结
- 【转帖】漫话C++0x(四) —- function, bind和lambda
- 8 个用于业余项目的优秀 Python 库
- Python练习 | WebServer