分析
这回试了一下三级标题,不知道效果怎么样?
回到正题,二维最长上升子序列......嗯,我会二维线段树。
考虑\(CDQ\)分治,算法流程:
先递归进入左子区间。
将左,右子区间按\(x\)排序。
归并处理左右子区间,在过程中使用树状数组加速\(DP\)。
还原右区间,清空树状数组。
递归进入右子区间。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#define lowbit(x) ((x)&(-(x)))
#define rin(i,a,b) for(int i=(a);i<=(b);i++)
#define rec(i,a,b) for(int i=(a);i>=(b);i--)
#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)
using std::cin;
using std::cout;
using std::endl;
typedef long long LL;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=100005;
int n,b[MAXN];
int siz;
int bit[MAXN];
struct Node{
int x,y,pos,f;
Node(){
f=1;
}
friend bool operator < (Node x,Node y){
return x.x==y.x?x.y<y.y:x.x<y.x;
}
}a[MAXN],c[MAXN];
inline void Add(int x,int kk){
for(int i=x;i<=siz;i+=lowbit(i)) bit[i]=(kk==-1?0:std::max(bit[i],kk));
}
inline int Ask(int x){
int ret=0;
for(int i=x;i;i-=lowbit(i)) ret=std::max(ret,bit[i]);
return ret;
}
inline bool cmp(Node x,Node y){
return x.pos<y.pos;
}
void cdq(int l,int r){
if(l>=r) return;
int mid=((l+r)>>1);
cdq(l,mid);
std::sort(a+l,a+mid+1);
std::sort(a+mid+1,a+r+1);
int lptr=l;
rin(rptr,mid+1,r){
while(lptr<=mid&&a[lptr].x<a[rptr].x){
Add(a[lptr].y,a[lptr].f);
lptr++;
}
a[rptr].f=std::max(a[rptr].f,Ask(a[rptr].y-1)+1);
}
rin(i,l,lptr-1) Add(a[i].y,-1);
rin(i,mid+1,r) c[i]=a[i];
rin(i,mid+1,r) a[c[i].pos]=c[i];
// std::sort(a+mid+1,a+r+1,cmp);
cdq(mid+1,r);
}
int main(){
n=read();
rin(i,1,n){
a[i].x=read();
b[i]=a[i].y=read();
a[i].pos=i;
}
std::sort(b+1,b+n+1);
siz=std::unique(b+1,b+n+1)-b-1;
rin(i,1,n) a[i].y=std::lower_bound(b+1,b+n+1,a[i].y)-b;
cdq(1,n);
int ans=1;
rin(i,1,n) ans=std::max(ans,a[i].f);
printf("%d\n",ans);
return 0;
}