【GDOI2018Day2模拟4.18】奥利卡的诗

本文主要是介绍【GDOI2018Day2模拟4.18】奥利卡的诗，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

这里写图片描述

Input

从文件poem.in中读入数据.
第一行两个整数n.
接下来若干行有n个单词，用空格或回车隔开.

Output

输出到文件poem.out中.
输出n行n个整数，第i个整数表示elegancy(i).

Sample Input

输入1：
2
nyg
nyx

Sample Output

输出1：
6
18

Data Constraint

$n<=10^5,\sum |s|<=3*10^5$

Solution

答案显然是每个子串的数量的平方和
子串数量，考虑SAM
对所有字符串建trie，然后建SAM
初始时所有点right集大小为0
用数据结构维护答案，因为right集的大小是在fail树上的，所以对fail树链剖然后用线段树维护平方和
注意一个状态中存储的字符串是[min,max]，而不是一个
所以方便一点的处理方法是每次修改时考虑统计1~r对r+1的贡献和r+1对1~r+1的贡献
具体看程序吧

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 1001000
#define ll long long
using namespace std;
int n,last[N],d[N],tr[N][26],tot=1,m,las[N],nxt[N],to[N],son[N],top[N],sz[N],fa[N],dfn[N],s[N],en[N];
ll ans=0;
struct{int fail,len,to[26];
}t[N];
struct{ll lz,v,s;
}g[N*3];
void putin(int x,int y)
{nxt[++tot]=las[x];las[x]=tot;to[tot]=y;
}
void add(int x,int las)
{int p=las,np=++tot;t[np].len=t[p].len+1;for(;p&&t[p].to[x]==0;p=t[p].fail) t[p].to[x]=np;if(p==0){t[np].fail=1;return;}int q=t[p].to[x];if(t[p].len+1==t[q].len) t[np].fail=q;else{int nq=++tot;t[nq]=t[q];t[nq].len=t[p].len+1;t[q].fail=t[np].fail=nq;for(;p&&t[p].to[x]==q;p=t[p].fail) t[p].to[x]=nq;}
}
void bfs()
{int he=0,ta=1;d[1]=1;while(he<ta){int x=d[++he];fo(i,0,25)if(tr[x][i]){d[++ta]=tr[x][i];last[tr[x][i]]=tot+1;add(i,last[x]);}}
}
void dg1(int x)
{sz[x]=1;for(int i=las[x];i;i=nxt[i]){int y=to[i];fa[y]=x;dg1(y);sz[x]+=sz[y];if(sz[y]>sz[son[x]]) son[x]=y;}
}
void dg2(int x)
{dfn[x]=++tot;if(son[x]) top[son[x]]=top[x],dg2(son[x]);for(int i=las[x];i;i=nxt[i]){int y=to[i];if(y==son[x]) continue;top[y]=y;dg2(y);}
}
void build(int v,int i,int j,int x,int y)
{if(i==j){g[v].v=t[y].len-t[t[y].fail].len;return;}int m=(i+j)/2;if(x<=m) build(v*2,i,m,x,y);else build(v*2+1,m+1,j,x,y);g[v].v=g[v*2].v+g[v*2+1].v;
}
void down(int v)
{if(g[v].lz==0) return;g[v*2].lz+=g[v].lz;g[v*2+1].lz+=g[v].lz;g[v*2].s+=g[v].lz*g[v*2].v;g[v*2+1].s+=g[v].lz*g[v*2+1].v;g[v].lz=0;
}
void ins(int v,int i,int j,int x,int y)
{if(i==x&&j==y){g[v].lz++;g[v].s=g[v].s+g[v].v;return;}int m=(i+j)/2;down(v);if(y<=m) ins(v+v,i,m,x,y);else if(x>m) ins(v+v+1,m+1,j,x,y);else ins(v+v,i,m,x,m),ins(v+v+1,m+1,j,m+1,y);g[v].s=g[v*2].s+g[v*2+1].s;
}
void get(int v,int i,int j,int x,int y)
{if(i==x&&j==y){ans+=g[v].s;return;}int m=(i+j)/2;down(v);if(y<=m) get(v+v,i,m,x,y);else if(x>m) get(v+v+1,m+1,j,x,y);else get(v+v,i,m,x,m),get(v+v+1,m+1,j,m+1,y);
}
void change(int x)
{x=last[x];int y=x;while(y>1){x=top[y];ins(1,1,m,dfn[x],dfn[y]);y=fa[x];}
}
void calc(int x)
{x=last[x];int y=x;while(y>1){x=top[y];get(1,1,m,dfn[x],dfn[y]);y=fa[x];}
}
int main()
{freopen("poem.in","r",stdin);freopen("poem.out","w",stdout);scanf("%d\n",&n);fo(i,1,n){int c=getchar()-97;int x=1;en[i]=en[i-1];for(;c>=0&&c<=26;c=getchar()-97){if(tr[x][c]==0) tr[x][c]=++tot;x=tr[x][c];s[++en[i]]=c;}}last[1]=tot=1;bfs();m=tot;tot=0;fo(i,2,m) putin(t[i].fail,i);tot=0;dg1(1);son[1]=0;dg2(1);fo(i,1,m)build(1,1,m,dfn[i],i);fo(i,1,n){int x=1;fo(j,en[i-1]+1,en[i]){x=tr[x][s[j]];calc(x);}x=1;fo(j,en[i-1]+1,en[i]){x=tr[x][s[j]];change(x);}x=1;fo(j,en[i-1]+1,en[i]){x=tr[x][s[j]];calc(x);}printf("%lld\n",ans);}
}