[CF1073G]LCP问题

• 题意：给一个长n的字符串S,q组询问，每组给两个集合A,B。求集合A中的点和集合B中的点所有组合情况的lcp的和。
• 思路：
  好像比较常规，可是代码能力差还是调了1.5h。主要还是虚树板子不熟（加入的时候点要去重）
  SAM+虚树+虚树上dp
  两个后缀的lca相当于后缀树上两个对应节点的LCA的len。
  dp就统计每个点为lca的方案数*len[lca]
• code:

#include
using namespace std;
const int N=4e5+5;
char s[N];
typedef long long ll;
int lg[N],a[N],b[N],d[N],pos[N],nxt[N],to[N],head[N],ecnt;
void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
struct SAM {
	int f[N][21],dep[N],ch[N][27],t[N],len[N],lst,num,par[N],sz[N],Head[N],To[N],Nxt[N],Ecnt,In[N],Out[N],Time;
	SAM() {lst=num=1;}
	void Add_edge(int u,int v) {Nxt[++Ecnt]=Head[u];To[Ecnt]=v;Head[u]=Ecnt;}
	int Insert(int x) {
		int p=lst,np=++num;lst=np;len[np]=len[p]+1;sz[np]=1;
		for(;!ch[p][x];p=par[p]) ch[p][x]=np;
		if(!p) {par[np]=1;return np;}
		int q=ch[p][x];
		if(len[q]==len[p]+1) {par[np]=q;return np;}
		int nq=++num;par[nq]=par[q];len[nq]=len[p]+1;
		for(int j=0;j<26;j++)ch[nq][j]=ch[q][j];
		par[q]=par[np]=nq;
		for(;ch[p][x]==q;p=par[p])ch[p][x]=nq;
		return np;
	}
	void dfs(int u) {
		In[u]=++Time;
		for(int i=Head[u];i;i=Nxt[i]) {
			int v=To[i];
			dep[v]=dep[u]+1;f[v][0]=u;
			for(int j=1;j<=lg[dep[v]];j++) f[v][j]=f[f[v][j-1]][j-1];
			dfs(v);
		}
		Out[u]=Time;
	}
	void bd_Fail() {
		for(int i=1;i<=num;i++) if(par[i])Add_edge(par[i],i);
		dfs(1);
	}
	int Lca(int u,int v) {
		if(dep[u]=0;i--) if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
		return f[u][0];
	}
}A;
bool cmp(int u,int v) {return A.In[u]=0;i--)pos[i+1]=A.Insert(s[i]-'a');
	lg[1]=0;for(int i=2;i<=(n<<1);i++)lg[i]=lg[i>>1]+1;
	A.bd_Fail();
	while(q--) {
		int ca,cb,up=0;
		scanf("%d%d",&ca,&cb);
		for(int i=1;i<=ca;i++) {scanf("%d",&a[i]);d[++up]=a[i]=pos[a[i]];mark[a[i]]=1;}
		for(int i=1;i<=cb;i++) {scanf("%d",&b[i]);b[i]=pos[b[i]];if(!mark[b[i]])d[++up]=b[i],mark[b[i]]=1;}
		sort(d+1,d+1+up,cmp);
		for(int i=1,sz=up;iA.Out[st[tp]]))tp--;
			if(tp)add_edge(st[tp],d[i]);
//			printf("!%d %d\n",st[tp],d[i]);
			st[++tp]=d[i];
		}
		for(int i=1;i<=ca;i++)sa[a[i]]=1;
		for(int i=1;i<=cb;i++)sb[b[i]]=1;
		DP(d[1]);
		printf("%lld\n",ans);
		tp=ecnt=ans=0;for(int i=1;i<=up;i++)mark[d[i]]=sa[d[i]]=sb[d[i]]=head[d[i]]=0;
	}
	return 0;
}