一片题解
怎么O(nlogn)搞一个最长上升子序列吧。
考虑一个数列5 2 3 1 4
首先，把5加入答案序列中，然后加2，发现2<5所以显然2替换5不会使结果更差，那么答案序列就是{2},然后加3，发现3>2，所以直接把3加到答案序列中：{2,3}
然后加1，我们发现1<3，于是我们找到一个最小的但是比1大的数字2，然后把1替换2，为什么这么做不会影响结果呢？你可以这么想，我们当前已经求出了一个当前最优的序列，如果我们用1替换2，然后后面来一个数字替换了3，那么我们就可以得到一个更优的序列，而如果没有数字替换3，那么这个1替换2也就是没有贡献的，不会影响我们结果的最优性。至于，如何找到一个最小的但是大于某个数字的数字，弄个二分查找就行了，因为我们的答案序列是有序的。
然后考虑如何解决这道题。
首先，我们可以想到，最长公共子序列，就是两段所含数字完全一样，并且数字的顺序也是完全一样的序列。
而顺序，我们可以想到类似哈希的思想，考虑建立一个类似map的关系数组f[ai]=i，那么我们找到的序列只要是上升的，顺序就是一样的，然后考虑数字完全一样，由于我们已经有了一个f[ai]=i,所以我们把对应的bi改成f[bi]，就可以确保数字相等了呀！
这时，就是在f[bi]的数组中求个最长上升子序列了，在二分查找。
洛谷p1439最长公共子序列
题目描述
给出1-n的两个排列P1和P2，求它们的最长公共子序列。
输入输出格式
输入格式：
第一行是一个数n，
接下来两行，每行为n个数，为自然数1-n的一个排列。
输出格式：
一个数，即最长公共子序列的长度
输入输出样例
输入样例#1：
5
3 2 1 4 5
1 2 3 4 5
输出样例#1：
3
代码如下
#include <bits/stdc++.h>
using namespace std;
int n,c,cnt = 0;
int a[100005],ans[100005];
map<int,int>q;
int main(){
cin>>n;
for(int i = 1;i <= n;i++)
{
scanf("%d",&c);
q[c] = i;
}
for(int i = 1;i <= n;i++)
{
scanf("%d",&c);
a[i] = q[c];
}
/* for(int i = 1;i <= n;i++) */
/* { */
/* printf("%d ",a[i]); */
/* } */
ans[1] = a[1];
int len = 1;
for(int i = 2;i <= n;i++)
{
if(ans[len] < a[i])
{
ans[++len] = a[i];
}
else{
int pos = lower_bound(ans,ans+len,a[i]) - ans;
ans[pos] = a[i];
}
}
printf("%d\n",len);
return 0;
}