排列LCS

Posted by Panda2134's Blog on July 24, 2017

题目链接: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:是达哥%%%%%%%

LIS与树状数组优化DP