济南seo网站优化公司,个人网站建设方案模板,企业做官网,南宁网站建设制作后台正题
题目链接:https://www.luogu.com.cn/problem/CF1276F 题目大意
给出一个长度为nnn的字符串SSS#xff0c;现在依次进行如下操作
取出SSS的一个子串TTT。将TTT中的一个字符替换成∗*∗号#xff08;也可以不替换#xff09;
求最后有多少种不同的TTT。 解题思路
发…正题
题目链接:https://www.luogu.com.cn/problem/CF1276F 题目大意
给出一个长度为nnn的字符串SSS现在依次进行如下操作
取出SSS的一个子串TTT。将TTT中的一个字符替换成∗*∗号也可以不替换
求最后有多少种不同的TTT。 解题思路
发现最终其实只有4种情况T,T∗,∗T,T1∗T2T,T*,*T,T_1*T_2T,T∗,∗T,T1∗T2。
前面三种很好记录主要考虑最后一种。
对于T1T_1T1来说同一个endposendposendpos等价类中的子串对应的T2T_2T2数量应该也是相同的。
那我们肯定是先建一个SAMSAMSAM这样就可以知道每个endposendposendpos等价类了。
那么考虑怎么统计T2T_2T2的数量其实对应iii在某个endposendposendpos里那么我们就只需要考虑从i2i2i2这些位置开始的不同串的数量。
也就是确定起始位置的子串这提醒我们反着再建立一个SAMSAMSAM然后把所有i2i2i2位置的点标记了这些点和根在failfailfail树上的虚树路径长度和就是我们要知道的答案。
那么怎么维护这个东西呢我们在正着的SAMSAMSAM上每个点维护一个线段树然后统计反着的SAMSAMSAM上的链并长度这个显然是可以用线段树合并的。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n)如果肯写O(1)O(1)O(1)LCA的话可以做到O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e510,MN5;
struct SAM{ll cnt,last,len[N],pos[N],fa[N],ch[N][26];void Ins(ll c,ll id){ll plast,nplastcnt;len[np]len[p]1;pos[id]np;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{ll qch[p][c];if(len[p]1len[q])fa[np]q;else{ll nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]fa[np]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return;}
}Suf,Pre;
struct node{ll to,next;
}a[N];
ll n,m,tot,cnt,ls[N],siz[N],dep[N],rt[N];
ll dfn[N],rfn[N],son[N],top[N],ans2;
char s[N];
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs1(ll x){siz[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;dep[y]dep[x]1;dfs1(y);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}return;
}
void dfs2(ll x){dfn[cnt]x;rfn[x]cnt;if(son[x]){top[son[x]]top[x];dfs2(son[x]);}for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yson[x])continue;top[y]y;dfs2(y);}return;
}
ll LCA(ll x,ll y){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);xSuf.fa[top[x]];}return (dep[x]dep[y])?x:y;
}
struct SegTree{ll cnt,ls[M],rs[M],w[M],pl[M],pr[M];void Merge(ll x){if(!ls[x]||!rs[x]){ll pls[x]|rs[x];w[x]w[p];pl[x]pl[p];pr[x]pr[p];}else{w[x]w[ls[x]]w[rs[x]]-Suf.len[LCA(pr[ls[x]],pl[rs[x]])];pl[x]pl[ls[x]];pr[x]pr[rs[x]];}return;}void Change(ll x,ll L,ll R,ll pos){if(!x)xcnt;if(LR){w[x]Suf.len[dfn[L]];pl[x]pr[x]dfn[L];return;}ll mid(LR)1;if(posmid)Change(ls[x],L,mid,pos);else Change(rs[x],mid1,R,pos);Merge(x);return;}ll Merge(ll x,ll y,ll L,ll R){if(!x||!y)return x|y;ll mid(LR)1;ls[x]Merge(ls[x],ls[y],L,mid);rs[x]Merge(rs[x],rs[y],mid1,R);Merge(x);return x;}
}T;
void solve(ll x){for(ll ils[x];i;ia[i].next){ll ya[i].to;solve(y);rt[x]T.Merge(rt[x],rt[y],1,cnt);}ansT.w[rt[x]]*(Pre.len[x]-Pre.len[Pre.fa[x]]);return;
}
signed main()
{scanf(%s,s1);nstrlen(s1);Pre.lastPre.cntSuf.lastSuf.cnt1;for(ll in;i1;i--)Suf.Ins(s[i]-a,i);for(ll i1;in;i)Pre.Ins(s[i]-a,i);for(ll i1;iPre.cnt;i)ansPre.len[i]-Pre.len[Pre.fa[i]];for(ll i1;iSuf.cnt;i)ansSuf.len[i]-Suf.len[Suf.fa[i]];Suf.Ins(s[1]-a,1);Pre.Ins(s[n]-a,n);for(ll i2;iSuf.cnt;i)addl(Suf.fa[i],i),ansSuf.len[i]-Suf.len[Suf.fa[i]];dfs1(1);top[1]1;dfs2(1);tot0;memset(ls,0,sizeof(ls));for(ll i2;iPre.cnt;i)addl(Pre.fa[i],i);for(ll i1;in-1;i)T.Change(rt[Pre.pos[i]],1,cnt,rfn[Suf.pos[i2]]);solve(1);printf(%lld\n,ans);return 0;
}
