首先对于双关键字的LIS有一个比较暴力的方法，就是线段树套平衡树，我们把双关键字的LIS抽象成二维坐标系中的点，这样我们对于当前转移的点i（x,y），需要找的就是在(xx,yy)xx<x,yy<y中的决策点的最大值是多少，这样我们用线段树维护第一维坐标，用sbt或者是线段树维护第二维坐标，这样就可以了。
但是树套树的常数非常大，将线段树改为BIT之后虽然对常数有一些优化，但还是较大，所以我们需要考虑另一种方法。
在求单关键字的LIS的时候，有一种nlogn的二分做法，大概意思是维护一个b[i]数组，对于第i位b[i]代表长度为i的上升子序列的最后一位最小的值，那么在二维的情况下，我们b[i]的每一位存一颗splay，splay中存的是每个决策点的信息，横向x递增，纵向y递减，因为对于同一长度的子序列，某一决策点(x,y)和另一决策点(x‘,y‘)，x<x‘,y<y‘，这种情况下的(x‘,y‘)决策点没什么作用，所以我们用这个splay维护一个上凸壳，对于当前的点(x,y)每次二分时，判断在二分的位置mid的splay中，x的位置值y的大小关系，最后将(x,y)这个点加入mid+1的splay中，同时维护这颗splay就好了。
spoj LIS2是这个的裸题，懒得写了= =。
原文：http://www.cnblogs.com/BLADEVIL/p/3562037.html