Description
已知两个长度为N的数组A和B，下标从0标号至N-1。
现在定义一种D序列 (假设长度为L)，这种序列满足下列条件：
1. 0 <= D[i] <= N-1
2. A[D[i]] < A[D[i+1]] (0 <= i < L-1)
3. B[D[i]] > B[D[i+1]] (0 <= i < L-1)
求满足条件的D序列的最大长度。
（其实这种序列叫做D序列的原因是：这道题是D题）
Input
多组数据，每组数据第一行是一个整数N。(1 <= N <= 100000)
第二行中有N个正整数A[0]~A[N-1]。
第三行中有N个正整数B[0]~B[N-1]。
保证所有输入整数在int范围内。
Output
对每组数据，输出一个整数，表示D序列的最大长度L。
Sample Input
3 1 1 2 3 2 1 3 1 2 3 3 2 1 4 1 3 2 4 3 1 2 4
Sample Output
233
思路：：将A数组，B数组以A为第一关键字，B为第二关键字进行升序排序，然后将B倒置求B的最长上升子序列。 为了避免下标排序和写比较函数，将A B 保存在pair里先排序，然后再取出来存放大到 A 中。倒置，并求最长子序列。 在求最长上升子序列时，直接用dp的方法时间复杂度为 O(n^2),会超时，所以采用其他的方法求。 方法（1）：：利用lower_bound 求上升子序列O(nlogn) //lower_bound三个参数分别为要比较的起始点地址，终止点的地址+1（也就是左闭右开），要比较的值(假设为d)。 //它的作用是返回一个地址，这个地址是在比较的范围内>=d的最小的值的地址。 //举个例子，a[] = {0 , 1 ,2, 4, 5, 7 } p =lower_bound(a,a+6,3),p就为 4 的地址，如果p =lower_bound(a,a+6,4),p也为 4 的地址 方法（2）：：利用二分法求上升子序列O(nlogn) 利用lower_bound要在数组中进行比较，当要比较的数较大时，无法将数存放在数组中，而利用二分法能解决这一问题，但代码难度较大。 两种方法的思路是一样的。将数组A中子序列长度为 i 的最小值存放在数组S中。我们以3 2 4 6 5 7 3 为例进行演示行为遍历，列为数组S，变化的地方已经标出来，有助于理解。在这里a[ i ] > s[ j ]&&a[i]<=s[ j + 1 ]就应该把a[ i ]放在s[ j+1 ]的位置。所以关键就是找出 j 就知道把a[ i ]放在哪了。上面的两种方法就是用来寻找 j的 。（在这里lower_bound直接返回 j + 1 ） 我们可以发现s数组中的值必然是有序递增的，这也是可以利用二分法的一个必要条件。
演示
| 0 |
1 |
2 |
3 |
4 |
| 1 |
3 |
? |
? |
? |
| 2 |
2 |
? |
? |
? |
| 3 |
2 |
4 |
? |
? |
| 4 |
2 |
4 |
6 |
? |
| 5 |
2 |
4 |
5 |
? |
| 6 |
2 |
4 |
5 |
7 |
| 7 |
2 |
3 |
5 |
7 |
| ? |
? |
? |
? |
? |
方法（1）代码：：
#include
using namespace std;
int a[100005],b[100005];
int s[100005];
vector
> T;//可以用vector存，也可以直接用数组 pair
T[100005]; int main() { int n; while(~scanf(%d,&n)){ T.clear();//如果不初始或要出错用数组就不需要了 for(int i = 0;i
第一个元素首先放入 s[1] for(int i = 1;i
s[len])s[++len] = a[i]; else{ int p = lower_bound(s+1,s+len+1,t)-s; s[p] = t; } } printf(%d ,len); } return 0; }
方法（2）代码：：
#include
using namespace std;
int a[100005],b[100005];
int s[100005];
vector
> T; int main() { int n; while(~scanf(%d,&n)) { T.clear(); for(int i = 0;i
s[len]) s[++len] = a[i]; else{ int l = 1,r = len,mid; int ans = 0; while(l<=r)//这里的二分法采用了左闭右闭的思路 { mid = (r+l)/2; if(s[mid]
?