简历怎么制作网站,房屋装修网,房城乡建设部门户网站,徐州网正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1600 题目大意
给出一个字符串sss#xff0c;每次在最后插入一个字符后求它的所有分别子串构出的failfailfail树的深度和。 1≤Q≤1051\leq Q\leq 10^51≤Q≤105 解题思路
考虑两个相等的子串长度为le…正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1600 题目大意
给出一个字符串sss每次在最后插入一个字符后求它的所有分别子串构出的failfailfail树的深度和。
1≤Q≤1051\leq Q\leq 10^51≤Q≤105 解题思路
考虑两个相等的子串长度为lenlenlen那么以后面那个子串末尾结尾的failfailfail有lenlenlen种左端点的情况是指向前面那个子串的。
新插入后所有串的后缀都是新的子串考虑如何统计这些串的答案首先不考虑最后一个位置那么深度和就是前面那次新加的深度和。现在只需要计算新插入那个字符在这nnn个串中的贡献我们可以找出所有和这些串的所有后缀相同的子串都会产生贡献这个可以用SAMSAMSAM统计。
所以可以考虑先把完整的串的SAMSAMSAM建出来再考虑做法每次插入一个字符串的时候先查询它在parentsparentsparents树上到根的路径的边权乘上边的长度和然后再向这条路径上每条边的权值加一。
注意到要路径加权求和所以要加一个树剖就可以了
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const int N4e510,P1e97;
struct node{int to,next;
}a[N];
int n,cnt,last,tot,dfc,p[N],ls[N];
int siz[N],son[N],top[N],dfn[N],rfn[N];
int fa[N],ch[N][26];ll len[N];
char s[N];bool v[N];
struct SegTree{ll w[N2],lazy[N2];void Downdata(int x,int L,int R){if(!lazy[x])return;int mid(LR)1;w[x*2](w[x*2]lazy[x]*(len[dfn[mid]]-len[dfn[L-1]]))%P;w[x*21](w[x*21]lazy[x]*(len[dfn[R]]-len[dfn[mid]]))%P;lazy[x*2]lazy[x];lazy[x*21]lazy[x];lazy[x]0;return;}void Change(int x,int L,int R,int l,int r){if(LlRr){(w[x]len[dfn[R]]-len[dfn[L-1]])%P;lazy[x];return;}int mid(LR)1;Downdata(x,L,R);if(rmid)Change(x*2,L,mid,l,r);else if(lmid) Change(x*21,mid1,R,l,r);else Change(x*2,L,mid,l,mid),Change(x*21,mid1,R,mid1,r);w[x](w[x*2]w[x*21]);return;}ll Ask(int x,int L,int R,int l,int r){if(LlRr)return w[x];int mid(LR)1;Downdata(x,L,R);if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return (Ask(x*2,L,mid,l,mid)Ask(x*21,mid1,R,mid1,r))%P;}
}T;
void Insert(int c){int plast,nplastcnt;len[np]len[p]1;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{int qch[p][c];if(len[q]len[p]1)fa[np]q;else{int nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]fa[np]nq;for(;ch[p][c]q;pfa[p])ch[p][c]nq;}}v[np]1;return;
}
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x){siz[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;dfs(y);siz[x]siz[y];len[y]len[y]-len[x];if(siz[y]siz[son[x]])son[x]y;}return;
}
void dfs2(int x){dfn[dfc]x;rfn[x]dfc;if(son[x]){top[son[x]]top[x];dfs2(son[x]);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yson[x])continue;top[y]y;dfs2(y);}return;
}
void print(int x)
{if(x9)print(x/10);putchar(x%1048);return;}
signed main()
{freopen(string.in,r,stdin);freopen(string.out,w,stdout);scanf(%d,n);scanf(%s,s1);lastcnt1;for(int i1;in;i)Insert(s[i]-a),p[i]last;for(int i2;icnt;i)addl(fa[i],i);top[1]1;dfs(1);dfs2(1);ll k0,ans0;for(int i1;icnt;i)len[dfn[i]](len[dfn[i]]len[dfn[i-1]])%P;for(int i1;in;i){int xp[i];while(x){k(kT.Ask(1,1,cnt,rfn[top[x]],rfn[x]))%P;xfa[top[x]];}ans(ansk)%P;xp[i];while(x){T.Change(1,1,cnt,rfn[top[x]],rfn[x]);xfa[top[x]];}print((ansP)%P);putchar(\n);}return 0;
}
