题目描述

Description

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

Sample Input

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

Sample Output

3

HINT

数据范围100000

题目分析

三维偏序CDQ
一维排序 一维归并排序 (我用的是无脑sort慢到死) 一维树状数组
最后注意离散化

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
struct your
{
    int x,y,id,sum;
}a[100400];
bool cmp(your j,your k)
{
    if(j.x==k.x) return j.y<k.y;
    return j.x<k.x;
}
int f[300010];
void add(int x,int c)
{
    for(;x<=200010;x+=x&-x)
        f[x]=max(f[x],c);
}
int ask(int x)
{
    int sum=0;
    for(;x;x-=x&-x) sum=max(sum,f[x]);
    return sum;
}
void clean(int x)
{
    for(;x<=200010;x+=x&-x)
        f[x]=0;
}
bool cmp2(your j,your k)
{
    return j.id<k.id;
}
void cdq(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid);
    sort(a+l,a+mid+1,cmp),sort(a+mid+1,a+r+1,cmp);
    for(int tmp=l,nmp=mid+1;nmp<=r;nmp++)
    {
        while(tmp<=mid&&a[tmp].x<a[nmp].x)
        {
            add(a[tmp].y,a[tmp].sum);
            tmp++;
        }
        a[nmp].sum=max(a[nmp].sum,ask(a[nmp].y-1)+1);
    }
    for(int i=l;i<=mid;i++) clean(a[i].y);
    sort(a+l,a+r+1,cmp2);
    cdq(mid+1,r);
}
struct my
{
    int x,y,id;
}b[100010*2];
bool cmp3(my j,my k)
{
    return j.x<k.x;
}
bool cmp4(my j,my k)
{
    return j.id<k.id;
}
int cc[2*100010];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i;
    for(int i=1;i<=n;i++) b[i*2-1].x=a[i].x,b[i*2].x=a[i].y,b[i*2-1].id=i*2-1,b[i*2].id=i*2;
    sort(b+1,b+n*2+1,cmp3);
    for(int i=1;i<=2*n;i++)
    {
        if(b[i].x!=b[i-1].x) cc[i]=cc[i-1]+1;
        else cc[i]=cc[i-1];
    }
    for(int i=1;i<=2*n;i++) b[i].x=cc[i];
    sort(b+1,b+2*n+1,cmp4);
    for(int i=1;i<=n;i++) a[i].x=b[i*2-1].x,a[i].y=b[i*2].x;
    cdq(1,n);
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,a[i].sum);
    printf("%d",ans);
    return 0;
}