题目描述

给定一个长度为N的序列S，S的每个元素pi是一个二元组(xi,yi)，定义pi<pj当且仅当xi<xj并且yi<yj，求S的最长上升子序列长度

输入格式

第一行一个N，表示一共有N个元素

接下来有N行，每行包含两个正整数xi,yi

输出格式

输出一行一个整数，代表序列S的最长上升子序列的长度

 

一道很好的模板题，比较入门吧

CDQ分治+线段树/树状数组维护最大值就好了

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 struct nasm{ 6     int x,y,z; 7 }a[100000]; 8 int f[1000000]; 9 int tr[1000000];10 int tmp[100000];11 int n;12 bool cmp(nasm g,nasm u)13 {14     return g.y
         
          >1;28     if(pi<=m)29         updt(pi,v,l,m,spc<<1);30     else    31         updt(pi,v,m+1,r,spc<<1|1);32     tr[spc]=max(tr[spc<<1],tr[spc<<1|1]);33 }34 int ask(int ll,int rr,int l,int r,int spc)35 {36     if(ll>rr)return 0;37     if(l>=ll&&r<=rr)return tr[spc];38     int m=(l+r)>>1;39     if(m>=rr)return ask(ll,rr,l,m,spc<<1);40     if(m
          
           >1;46     sort(a+l,a+mid+1,cmp);47     sort(a+mid+1,a+r+1,cmp);48     for(int i=l,j=mid+1;j<=r;j++)49     {50         for(;a[i].y
           
            <=mid;i++)51 updt(a[i].z,f[a[i].x],1,n,1);52 f[a[j].x]=max(f[a[j].x],ask(1,a[j].z-1,1,n,1)+1);53 }54 for(int i=l;i<=mid;i++)updt(a[i].z,0,1,n,1);55 sort(a+mid+1,a+r+1,cmq);56 }57 void cdq(int l,int r)58 {59 if(l==r)60 return ;61 int mid=(l+r)>>1;62 cdq(l,mid);63 wrk(l,r);64 cdq(mid+1,r);65 66 }67 int erf(int l,int r,int aim)68 {69 if(l==r)return l;70 int m=(l+r)>>1;71 if(aim<=tmp[m])72 return erf(l,m,aim);73 return erf(m+1,r,aim);74 }75 int main()76 {77 scanf("%d",&n);78 for(int i=1;i<=n;i++)79 {80 scanf("%d%d",&a[i].y,&a[i].z);81 f[i]=1;82 a[i].x=i;83 tmp[i]=a[i].z;84 }85 sort(tmp+1,tmp+n+1);86 for(int i=1;i<=n;i++)87 a[i].z=erf(1,n,a[i].z);88 cdq(1,n);89 int ans=0;90 for(int i=1;i<=n;i++)91 ans=max(ans,f[i]);92 printf("%d\n",ans);93 return 0;94 }