【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2225

【题目大意】

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

【题解】

  CDQ分治,将每个区间按照a排序,用区间左边的数据来更新右边的最长上升序列,
  为排除a相等但是b上升情况的误统计,在排序时加入下标作为第二关键字,
  使得a相等的情况下标小的后更新。

【代码】

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
int n,a[N],b[N],c[N],d[N],dp[N],p[N],q[N];
bool cmp(int x,int y){
if(a[x]==a[y])return x>y;
return a[x]<a[y];
}
void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
CDQ(l,mid);
for(int i=l;i<=r;i++)q[i]=i;
sort(q+l,q+r+1,cmp);
for(int i=l;i<=r;i++){
if(q[i]<=mid)for(int j=b[q[i]];j<=p[0];j+=j&-j)c[j]=max(c[j],dp[q[i]]);
else for(int j=b[q[i]]-1;j;j-=j&-j)dp[q[i]]=max(dp[q[i]],c[j]+1);
}for(int i=l;i<=r;i++)if(q[i]<=mid)for(int j=b[q[i]];j<=p[0];j+=j&-j)c[j]=0;
CDQ(mid+1,r);
}
int main(){
while(~scanf("%d",&n)){
p[0]=0;
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),p[++p[0]]=b[i],dp[i]=1;
sort(p+1,p+p[0]+1);
p[0]=unique(p+1,p+p[0]+1)-p-1;
for(int i=1;i<=n;i++)b[i]=lower_bound(p+1,p+p[0]+1,b[i])-p;
CDQ(1,n); int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
printf("%d\n",ans);
}return 0;
}
05-11 15:39
查看更多