Another Longest Increasing Subsequence Problem
有两种思路。
思路一：
考虑到如果只有一维，那么可以用f[s]表示长度为s时，最后一个数是多少，把这个想法拓展到二维，即f[s]表示长度为s时，最后一个点的集合，也就是说有多个点，但是这多个点是有顺序，x递增，y递减，并且每次加点进来的时候，随时保持这个顺序。
关于怎么处理点的集合，可以用平衡树来实现，这里用map来代替，而且map自带二分查找的功能。
算法实现：采用二分答案的方法，初始区间是(0,ans)这是刚好合适的情况，每次二分的时候，要验证两个值mid和mid+1，如果只验证mid，成立的时候跳向(mid+1,r)，但是这个区间上可能找不到答案，这和二分查找不一样，这是找最优解，而不是验证存不存在，所以至少要保证mid+1成立才能考查右区间。
最后更新的时候，记住保持x递增，y递减的顺序就可以了，情况比较多，很繁琐，我在这里错了很久，注意边界处的细节怎么处理，详细的看代码。
代码如下：
#include<bits/stdc++.h>
#define rep(i,n) for(i=1;i<=n;i++)
#define F first
#define S second
using namespace std;
const int maxn=100100;
map<int,int>f[maxn];
int n;
int find(int x,int y,int l,int r)
{
if(l==r)return l;
int mid=(l+r)>>1;
map<int,int>::iterator it1,it2;
it1=f[mid].lower_bound(x);
it2=f[mid+1].lower_bound(x);
if(it1==f[mid].begin() || it2==f[mid+1].begin())return find(x,y,l,mid);
--it1,--it2;
if(it1->S>=y || it2->S>=y)return find(x,y,l,mid);
return find(x,y,mid+1,r);
}
void update(int x,int y,int p)
{
map<int,int>::iterator it1=f[p].lower_bound(x),it2=it1;
if(it1!=f[p].end() && it1->F == x && it1->S<=y)return ;
if(it1!=f[p].begin() && (--it1)->S<=y)return ;
while(it2!=f[p].end() && it2->S>=y)f[p].erase(it2++);
f[p][x]=y;
}
int main()
{
int i,ans=0;
scanf("%d",&n);
f[0][-2000000000]=-2000000000;
rep(i,n)
{
int x,y;
scanf("%d%d",&x,&y);
int pos=find(x,y,0,ans);
ans=max(ans,++pos);
update(x,y,pos);
}
printf("%d",ans);
}
原文：http://www.cnblogs.com/xionglinlin/p/5030765.html