Problem Link

题目大意

给定序列 $a,b$，求一个公共子序列 $C$ 使得所有 $A,B$ 的公共子序列都是 $C$ 的子序列，或报告不存在。

数据范围：$n=|a|,m=|b|\le 10^5$。

思路分析

先考虑保证有解（记为 $c$）的情况。

如果一种字符在 $a$ 中出现 $x$ 次，$b$ 中出现 $y$ 次，那么这种字符必须在 $c$ 中出现 $\min(x,y)$ 次。

那么把出现次数较少的一侧的元素标记为关键位，我们要把所有关键位在另一个序列中找到匹配，且匹配两两不交。

考虑两个序列中的第一个关键位 $a_p,b_q$，如果他们相等，直接匹配即可。

如果 $a_p$ 在 $b[1,q)$ 中未出现，则必须 $b_q$ 匹配 $a[1,p)$，反之亦然。

如果 $a_p\in b[1,q)$ 且 $b_q\in a[1,p)$，还要进一步分析决策。

如果 $a(p,n]$ 中 $b_q$ 的出现次数小于 $b[q,m]$ 中的出现次数，那么 $a_p$ 不能匹配 $b[1,q)$，反之亦然。

加上这个限制后每个点的决策唯一。

如果此时两个条件同时满足：考虑 $a_pb_q\dots b_q$，$b_q$ 个数等于 $b[q,m]$ 中所有 $b_q$ 个数，这个序列是 $a,b$ 的子序列，且为了保证 $c$ 包含这个子序列，$a_p$ 必须匹配 $b[1,q)$。

类似构造 $b_qa_p\dots a_p$ 就导出了矛盾，因此这种情况直接会让答案无解。

那么构造一个可能解的时间复杂度 $\mathcal O(n+m)$。

接下来只要对 $c$ 进行判定是否正确。

构造一个 LCS $c'$ 使得 $c'$ 不是 $c$ 的子序列。

依次加入 $c'$ 的每个字符，维护在 $a,b,c$ 的子序列自动机上状态 $a_p,b_q,c_r$，以及 $c_r$ 对应 $a,b$ 中的字符 $a_{p'},b_{q'}$。

显然 $p\le p',q\le q'$，如果 $p<p',q<q'$ 同时成立，那么我们直接加上 $c[r,|c|]$ 的序列，一定能匹配 $a,b$ 且匹配不上 $c$。

可以证明 $c$ 不合法当且仅当出现 $p<p',q<q'$ 的情况。

首先 $p=p',q=q'$ 的状态最多转移到 $p<p',q=q'$ 或 $p=p',q<q'$ 的状态。

考虑一个 $p=p',q<q'$ 的状态下一步的转移，设下一个字符为 $c$，如果 $c$ 不在 $b(q,q']$，那么和 $q=q'$ 是等价的。

否则转移后的 $q$ 依然 $<q'$，只要判断是否有 $p<p'$ 即可，可以证明不合法状态只能从这种情况或对称状态转移而来。

我们枚举这种时候的 $p$（必须是非关键字符），然后算出能走到 $p$ 时最小的 $q$。

如果存在 $r$ 使得 $p'_r<p,q\le q'_r$ 那么不合法，因为此时的字符串一定走到 $c_{r}$ 后面的位置。

维护最小的 $q$（记为 $f_p$）相当于在 $f_{lst_p}\sim f_{p-1}$ 中找最小值，然后子序列自动机上添加字符 $a_p$，可以单调栈维护 + 二分维护。

时间复杂度 $\mathcal O((n+m)(\log n+\log m))$。

代码呈现

#include<bits/stdc++.h>
#include"hieroglyphs.h"
using namespace std;
const int MAXN=1e5+5,V=2e5;
struct ds {
	int n,p=1,a[MAXN],ps[V+5],nxt[V+5],ct[V+5];
	void init() {
		for(int i=0;i<=V;++i) ps[i]=n+1;
		for(int i=n;i>=1;--i) nxt[i]=ps[a[i]],ct[i]=ct[nxt[i]]+1,ps[a[i]]=i;
	}
	int q(int x) { return ct[ps[x]]; }
	void del(int x) { for(;p<x;++p) ps[a[p]]=nxt[p]; }
}	ca,cb,va,vb;
int n,m,a[MAXN],b[MAXN],k,c[MAXN],p[MAXN],q[MAXN];
int st[MAXN],f[MAXN],ps[V+5];
vector <int> o[V+5];
bool chk() {
	for(int i=0;i<=V;++i) o[i].clear(),ps[i]=0;
	for(int i=1;i<=m;++i) o[b[i]].push_back(i);
	int tp=0;
	for(int i=1,j=0;i<=n;++i) {
		int x=a[i];
		f[i]=f[*lower_bound(st,st+tp+1,ps[x])];
		f[i]=(o[x].empty()||o[x].back()<=f[i])?m+1:*upper_bound(o[x].begin(),o[x].end(),f[i]);
		while(p[j+1]<i) ++j;
		if(p[j+1]!=i&&f[i]<=q[j]) return false;
		while(tp&&f[st[tp]]>=f[i]) --tp;
		st[++tp]=i,ps[x]=i;
	}
	return true;
}
vector<int> ucs(vector<int>A,vector<int>B) {
	n=ca.n=va.n=A.size(),m=cb.n=vb.n=B.size();
	for(int i=1;i<=n;++i) a[i]=ca.a[i]=va.a[i]=A[i-1];
	for(int i=1;i<=m;++i) b[i]=cb.a[i]=vb.a[i]=B[i-1];
	ca.init(),cb.init(),va.init(),vb.init();
	vector <int> pa,pb;
	for(int i=1;i<=n;++i) if(ca.q(a[i])<=cb.q(a[i])) pa.push_back(i);
	for(int i=1;i<=m;++i) if(cb.q(b[i])<ca.q(b[i])) pb.push_back(i);
	auto it=pa.begin(),jt=pb.begin();
	for(int oa=0,ob=0;it!=pa.end()||jt!=pb.end();) {
		int i=(it==pa.end()?n+1:*it),j=(jt==pb.end()?m+1:*jt);
		va.del(oa+1),vb.del(ob+1),ca.del(i),cb.del(j);
		bool fa=i<=n&&vb.q(a[i])>cb.q(a[i])&&cb.q(b[j])<=ca.q(b[j]);
		bool fb=j<=m&&va.q(b[j])>ca.q(b[j])&&ca.q(a[i])<=cb.q(a[i]);
		if(fa==fb) return {-1};
		if(fa) ++k,c[k]=a[i],p[k]=i,q[k]=vb.ps[a[i]],vb.del(q[k]+1),oa=i,++it;
		else   ++k,c[k]=b[j],p[k]=va.ps[b[j]],q[k]=j,va.del(p[k]+1),ob=j,++jt;
	}
	p[k+1]=n+1,q[k+1]=m+1;
	if(!chk()) return {-1};
	swap(n,m),swap(a,b),swap(p,q);
	if(!chk()) return {-1};
	return vector<int>(c+1,c+k+1);
}