BZOJ_2225_[Spoj 2371]Another Longest Increasing_CDQ 分治+树状数组

Description

给定N个数对(xi, yi)，求最长上升子序列的长度。上升序列定义为{(xi, yi)}满足对i<j有xi<xj且yi<yj。

Input

Output

Sample Input

8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6

Sample Output

HINT

数据范围100000

有点烦的一道题。

有DP方程F[i]=F[j]+1(j<i&&x[j]<x[i]&&y[j]<y[i])

处理方法：先处理左边的F值，再处理左边的F转移到右边的F的情况，然后处理右边的F值。

递归完左边是这样一种情形，左边按x排序，右边无序(还没递归到)。

于是先把右边按x排序，然后维护一个指针在左边移动，每次在树状数组里更新f的最大值。

然后递归右边之后把两边的按x归并上去。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
int xx[N],yy[N],f[N],ans,t[N],T[N],n,V[N],cnt,tmp[N];
void fix(int x,int v) {for(;x<=n;x+=x&(-x)) T[x]=max(T[x],v);}
int inq(int x) {int re=0;for(;x;x-=x&(-x)) re=max(re,T[x]); return re;}
void clear(int x) {for(;x<=n;x+=x&(-x)) T[x]=0;}
bool cmp(int x,int y) {return xx[x]<xx[y];}
void solve(int l,int r) {
    if(l==r) {
        f[l]=max(f[l],1); 
        return ;
    }
    int mid=(l+r)>>1;
    int i=l,j=l,k=mid+1;
    solve(l,mid);
    for(i=mid+1;i<=r;i++) {
        tmp[i]=t[i];
    }
    sort(tmp+mid+1,tmp+r+1,cmp);
    for(i=mid+1;i<=r;i++) {
        while(j<=mid&&xx[t[j]]<xx[tmp[i]]) fix(yy[t[j]],f[t[j]]),j++;
        f[tmp[i]]=max(f[tmp[i]],inq(yy[tmp[i]]-1)+1);
    }
    for(i=l;i<j;i++) clear(yy[t[i]]);
    solve(mid+1,r);
    i=l,j=l,k=mid+1;
    while(j<=mid&&k<=r) {
        if(xx[t[j]]<xx[t[k]]) tmp[i++]=t[j++];
        else tmp[i++]=t[k++];
    }
    while(j<=mid) tmp[i++]=t[j++];
    while(k<=r) tmp[i++]=t[k++];
    for(i=l;i<=r;i++) t[i]=tmp[i];
}
int main() {
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++) scanf("%d%d",&xx[i],&yy[i]),t[i]=i,V[i]=yy[i];
    sort(V+1,V+n+1);
    cnt=unique(V+1,V+n+1)-V-1;
    for(i=1;i<=n;i++) yy[i]=lower_bound(V+1,V+cnt+1,yy[i])-V;
    // sort(t+1,t+n+1,cmp);
    solve(1,n);
    for(i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d\n",ans);
}

秒客网