Solution -「CF 1073G」Yet Another LCP Problem
Description
Link.
给定字符串，正整数集合 \(A,B\)，满足 \(\forall u\in A,v\in B,1\le u,v\le n\)。
求 \(\sum_{i\in A}\sum_{j\in B}\text{LCP}(A,B)\)。
Solution
双倍经验是 SvT，只不过 SvT 这屑玩意儿卡常。
先反转串，然后插入 SAM。众所周知
把字符串反转后插入 SAM 后，两个原串的后缀在 parent tree 上的 \(\text{LCA}\) 是这两个后缀的 \(\text{LCP}\)。
然后你就可以搞两个 DP，分别跑 \(A\) 子树大小，\(B\) 子树大小。
注意根节点需要特殊处理，因为我们是跨子树跑的 DP。不过 SvT 不需要，不知道是不是我的问题（应该就是）。
#include<bits/stdc .h>using namespace std;typedef long long LL;int n,m,dfn[500010],fa[500010][21],dep[500010],sjc,pos[200010],onepower[500010],anopower[500010],onef[500010],anof[500010];char s[200010];LL ans;struct SuffixAutomaton{#define ID(c) ((c)-'a')vector<int> e[500010];int n,cntot,las,len[500010],pre[500010],ch[500010][26];char s[200010];void init(int _n,char c[]){n=_n;for(int i=1;i<=n; i)s[i]=c[i];cntot=las=1;}void extend(char c){int cur= cntot,one=las,ano=0;len[cur]=len[las] 1,las=cur;while(one&&!ch[one][ID(c)])ch[one][ID(c)]=cur,one=pre[one];if(one==0)pre[cur]=1;else{ano=ch[one][ID(c)];if(len[one] 1==len[ano])pre[cur]=ano;else{int clone= cntot;len[clone]=len[one] 1;pre[clone]=pre[ano];memcpy(ch[clone],ch[ano],sizeof(ch[ano]));while(one&&ch[one][ID(c)]==ano)ch[one][ID(c)]=clone,one=pre[one];pre[ano]=pre[cur]=clone;}}}void build(){for(int i=1;i<=n; i)extend(s[i]),pos[i]=las;for(int i=2;i<=cntot; i)e[pre[i]].emplace_back(i);}}SAM;void dfs(int x,int las){dfn[x]= sjc,fa[x][0]=las,dep[x]=dep[las] 1;for(int i=1;i^21; i)fa[x][i]=fa[fa[x][i-1]][i-1];for(int y : SAM.e[x])dfs(y,x);}int LCA(int one,int ano){if(dep[one]<dep[ano])swap(one,ano);for(int i=20;~i;--i)if(dep[fa[one][i]]>=dep[ano])one=fa[one][i];if(one^ano){for(int i=20;~i;--i)if(fa[one][i]^fa[ano][i])one=fa[one][i],ano=fa[ano][i];return fa[one][0];}elsereturn one;}bool cmp(int one,int ano){return dfn[one]<dfn[ano];}struct VirtualTree{vector<int> e[500010];vector<int> build(vector<int> poi){sort(poi.begin(),poi.end(),cmp);poi.erase(unique(poi.begin(),poi.end()),poi.end());int len=poi.size();for(int i=1;i<len; i)poi.push_back(LCA(poi[i-1],poi[i]));sort(poi.begin(),poi.end(),cmp);poi.erase(unique(poi.begin(),poi.end()),poi.end());len=poi.size();for(int i=1;i<len; i)e[LCA(poi[i-1],poi[i])].push_back(poi[i]);return poi;}}VRT;template<class T>void read(T &hhh){T x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3) (x<<1) (c^'0'),c=getchar();if(~f)hhh=x;elsehhh=-x;}template<class T>void write(T x,char las='\n'){static int st[100],top=0;if(x<0)putchar('-'),x=-x;do st[ top]=x,x/=10; while(x);while(top)putchar(st[top--]^'0');putchar(las);}void exdfs(int x){for(int y : VRT.e[x])exdfs(y),onef[x] =onef[y],anof[x] =anof[y];for(int y : VRT.e[x])ans =(LL)SAM.len[x]*(onef[x]-onef[y])*anof[y];ans =(LL)((onepower[x]&anopower[x]) onepower[x]*anof[x] anopower[x]*onef[x])*SAM.len[x];onef[x] =onepower[x],anof[x] =anopower[x];}int main(){read(n),read(m);scanf("%s",s 1);reverse(s 1,s n 1);SAM.init(n,s),SAM.build();dfs(1,0);while(m--){int ones,anos,x;read(ones),read(anos);vector<int> key,tmp;while(ones--)read(x),key.push_back(pos[n-x 1]),onepower[pos[n-x 1]]=1;while(anos--)read(x),key.push_back(pos[n-x 1]),anopower[pos[n-x 1]]=1;tmp=VRT.build(key);ans=0,exdfs(tmp[0]);write(ans);for(int now : tmp)onef[now]=anof[now]=0,VRT.e[now].clear(),onepower[now]=anopower[now]=0;}return 0;} 赞 (0)