题目链接：Luogu-P1439
思路
按照题目中数据规模，直接跑LCS，复杂度为$O(n^2)$，只有50分。
考虑到题目中给定的是两个排列，应该可以利用排列的某些性质。
如果其中一个排列是$1,2,3,…,N$，那么显然LCS就是另一个排列的LIS。 如果两个排列都不是$1,2,3,…,N$呢？ 考虑把两个排列，通过同一种映射关系,进行转化，使得其中一个排列变为$1,2,3,…,N$。 这样转化是因为LCS与实际的每项的值无关，而与两项是否相同有关。 显然，这样转化，不会改变序列的LCS长度，因为原来相同的元素，通过映射得到的元素仍然相同。
举个栗子：
3 2 1 4 5 ···①
1 4 2 5 3 ···②
想要把第一个排列转为1,2,3,4,5，方法就是使①中的每项映射到自己的序号，再对②中每一项应用同一个映射。
此处的映射关系就是：
3->1, 2->2, 1->3, 4->4, 5->5
转化后就变为了
1 2 3 4 5 ···①
3 4 2 5 1 ···②
再跑一遍LIS即可。 LIS的经典做法是枚举以某个位置$i$为终点的LIS，枚举它前面的每一项，并进行更新。 这样的时间复杂度也是$O(n^2)$，所以为何要把LCS转为LIS呢？因为LIS问题可以优化。下面我们就试着把LIS问题优化到$O(N \log N)$
为了便于优化，常常需要修改状态。状态定义为 $ f(i) $：以数字i结尾的LIS长度。
从左往右扫原数组时，更新LIS： $ f(i)=max\{f(j)|j>i\} $
由于是从左向右扫的，一定是用$f(i)$左边的状态去更新$f(i)$,因此合法。
需要求出$f(i)$左侧的$f(j)$的最大值，以及单点修改，用树状数组维护即可。
实际上就是按权值建树状数组。
这样的时间复杂度为$O(N \log N)$，由于$N \leq 100000$，可以AC。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#define REP(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int MAXN = 100000;
int N,Ans,opt[MAXN+10],Mp[MAXN+10];
int front=1,rear=0,Q[2*MAXN+10],C[MAXN+10];
int A[MAXN+10],B[MAXN+10];
inline int lowbit(int x){
return x&(-x);
}
inline int query(int x){ //Prefix Mininum
int ret=0;
while(x>0){
ret=max(ret,C[x]);
x-=lowbit(x);
}
return ret;
}
inline void add(int x,int v){
while(x<=N){
C[x]=max(C[x],v);
x+=lowbit(x);
}
}
int main(){
scanf("%d",&N);
REP(i,N) scanf("%d",&A[i]);
REP(i,N) scanf("%d",&B[i]);
REP(i,N) A[i]=Mp[A[i]]=i;
REP(i,N) B[i]=Mp[B[i]];
REP(i,N){
opt[B[i]]=max(query(B[i]-1)+1,1);
add(B[i],opt[B[i]]);
}
REP(i,N) Ans=max(Ans,opt[i]);
printf("%d",Ans);
}
Credits
在某位dalao的blog上看到的树状数组优化LIS。先%为敬。 UPD:是达哥%%%%%%%
