[CF1073G]LCP问题

题意：给一个长n的字符串S,q组询问，每组给两个集合A,B。求集合A中的点和集合B中的点所有组合情况的lcp的和。
思路：

好像比较常规，可是代码能力差还是调了1.5h。主要还是虚树板子不熟（加入的时候点要去重）

SAM+虚树+虚树上dp

两个后缀的lca相当于后缀树上两个对应节点的LCA的len。

dp就统计每个点为lca的方案数*len[lca]
code:

#include<bits/stdc++.h>

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]<dep[v])swap(u,v);

		int k=dep[u]-dep[v];for(int i=0;i<=lg[k];i++)if((1<<i)&k)u=f[u][i];

		if(u==v) return u;

		for(int i=lg[dep[u]];i>=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]<A.In[v];}

int sa[N],sb[N],st[N],tp;

ll ans=0;

void DP(int u) {

//	printf("#%d %d\n",u,A.len[u]);

	ans+=1ll*A.len[u]*(sa[u]*sb[u]);

	for(int i=head[u];i;i=nxt[i]) {

		int v=to[i];

		DP(v);

		ans+=A.len[u]*(1ll*sa[v]*sb[u]+1ll*sa[u]*sb[v]);

		sa[u]+=sa[v],sb[u]+=sb[v];

	}

}

bool mark[N];

int main() {

	int n,q;scanf("%d%d",&n,&q);

	scanf("%s",s);

	for(int i=n-1;i>=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;i<sz;i++) {

			d[++up]=A.Lca(d[i],d[i+1]);

			if(mark[d[up]])up--;else mark[d[up]]=1;

		}

		sort(d+1,d+1+up,cmp);

//		puts("");for(int i=1;i<=up;i++) printf("%d ",d[i]);puts("");

		st[++tp]=d[1];

		for(int i=2;i<=up;i++) {

			int u=A.In[d[i]];

			while(tp&&(u<A.In[st[tp]]||u>A.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;

}

巴特西

[CF1073G]LCP问题

最新文章

热门文章