UVa 481 - What Goes Up

題目：最大上升子序列。

分析：dp、lis、二分、單調隊列。LIS的O(nlogn)算法。此算法，利用單調隊列+二分優化。單調隊列裡的元素Q[i]為，到目前為止、長度為i的LIS中最小的結束元素。運行過程中，如果當前元素小於隊尾元素，則可以和前面的構成LIS，直接加入隊尾，否則替換之前的長度相同的LIS的結尾元素，使對應位置上的元素變小，由於隊列滿足單調性，所以利用二分查找提高效率。例如：序列為：{1，3，2，3}，則計算過程Q為：{1}，{1，3}，{1，2}，{1，2，3}。這樣做是因為，如果{1,3}可以構成LIS的前綴串，那麼{1,2}必然可以構成LIS的前綴傳，並且可以接納更多的後綴。 www.2cto.com

注意：數據規模較大O(n^2)算法會TLE、求的是最後的LIS利用單調隊列直接滿足。

[cpp] 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
int data[ 100000 ]; 
int length[ 100000 ]; 
int front[ 100000 ]; 
int Q[ 100000 ]; 
 
void output( int v ) 
{ 
    if ( front[v] )  
        output( front[v] ); 
    printf("%d\n",data[v]); 
} 
 
int bs( int r, int v ) 
{ 
    int l = 1; 
    while ( l < r ) { 
        int mid = (l+r)>>1; 
        if ( data[Q[mid]] < v ) 
            l = mid+1; 
        else r = mid; 
    } 
    return r; 
} 
 
int main() 
{ 
    int count = 1; 
    while ( scanf("%d",&data[count]) != EOF ) 
        count ++; 
     
    int tail = 0; 
    Q[++ tail] = 1; 
    for ( int i = 2 ; i < count ; ++ i )  
        if ( data[Q[tail]] < data[i] ) { 
            Q[++ tail] = i; 
            front[i] = Q[tail-1]; 
        }else { 
            int id = bs( tail, data[i] ); 
            Q[ id ] = i; 
            front[i] = Q[id-1]; 
        } 
         
    printf("%d\n-\n",tail); 
    output( Q[tail] ); 
    return 0; 
}