题意：LIS最长递增子序列　　O(nlogn)

分析：设当前最长递增子序列为len，考虑元素a[i]; 若d[len]<a[i]，则len++，并使d[len]=a[i]; 否则,在d[1~len]中二分查找第一个大于等于a[i]的位置j，使d[j]=a[i]。附上打印路径代码(准确性未知)

 

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;int a[N], d[N], pos[N], fa[N];int n;void LIS(void)	{	int len = 1;	d[1] = a[1];	fa[1] = -1;	for (int i=2; i<=n; ++i)	{		if (d[len] < a[i])	{			d[++len] = a[i];			// pos[len] = i;	fa[i] = pos[len-1];		}		else	{			int j = lower_bound (d+1, d+1+len, a[i]) - d;			d[j] = a[i];			// pos[j] = i;	fa[i] = (j == 1) ? -1 : pos[j-1];		}	}	printf ("%d\n", len);	// vector
         
           res;	int i;	// for (i=pos[len]; ~fa[i]; i=fa[i])	res.push_back (a[i]);	// res.push_back (a[i]);	// for (int i=res.size ()-1; i>=0; --i)	printf ("%d%c", res[i], i == 0 ? '\n' : ' ');}int main(void)	{	while (scanf ("%d", &n) == 1)	{		for (int i=1; i<=n; ++i)	{			scanf ("%d", &a[i]);		}				LIS ();	}	return 0;}