[BZOJ2225][SP2371]LIS2 - Another Longest Increasing Subsequence Problem：CDQ分治+树状数组

分析

这回试了一下三级标题，不知道效果怎么样？

回到正题，二维最长上升子序列......嗯，我会二维线段树。

考虑\(CDQ\)分治，算法流程：

1. 先递归进入左子区间。

2. 将左，右子区间按\(x\)排序。

3. 归并处理左右子区间，在过程中使用树状数组加速\(DP\)。

4. 还原右区间，清空树状数组。

5. 递归进入右子区间。

代码

#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; 
}