zoj1986||poj1631BridgingSignals（最长上升子序列N*logN）

和ZOJ 2316 差不多，不过这个是用单调队列+二分优化了，不优化过不去。

单调队列是保证里面元素是单调的，这样的话，取其中最大的值是O(1)的，如果有数比队尾元素小，就用二分查找，找到它的位置替换。

原理详见http://blog.csdn.net/Hashmat/archive/2010/09/14/5883605.aspx

我的二分写得比较纠结，改了好久才对 = =。。。

#include <stdio.h>#include <stdlib.h>#include <iostream>#include <string.h>using namespace std;int Q[40002];int tail;int find(int low,int high,int x){if( low = 1 && low == high )if( x <= Q[1] )return 1;elsereturn -1;while( low <= high ){int mid = (low+high)/2;if( Q[mid] <= x && Q[mid+1] >= x )return mid+1;if( Q[mid] >= x )high = mid;if( Q[mid] <= x )low = mid+1;}return -1;}int main(void){int ncases;int num[40002],n;scanf("%d",&ncases);while( ncases-- ){cin >> n;tail = 1;memset(Q,0,sizeof(Q));for(int i=1; i<=n; i++)scanf("%d",&num[i]);Q[tail] = num[1];for(int i=2; i<=n; i++){int x = find(1,tail,num[i]);if( x == -1 ){tail++;Q[tail] = num[i];}elseQ[x] = num[i];}printf("%d/n",tail);}return 0;}