令${strleft(i,j ight)}$为区间${[l,r]}$所表示的子串。
对于任意$r$
一,求${sum _{i=1}^{n}sum _{j=i+1}^{n}[str(i,i+r-1)=str(j,j+r-1)]}$
二,求${ans[r]=max(val[i]*val[j])}$,且${str(i,i+r-1)=str(j,j+r-1)}$
直接用SAM构出后缀树，然后一个子串一定是原串的一个后缀的前缀，然后找到后缀树中每一个后缀对应的节点，每一对后缀的LCP对应了后缀树中的相应点的LCA的len(即代表的最长串的长度)，然后做一遍树形统计统计第一问答案，第二问答案即要记一下子树最大值最小值即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1000100 10 #define llg long long 11 #define SIZE 26 12 #define inf (((llg)1e18)+10) 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 14 llg n,m,ans1[maxn<<1],ans2[maxn<<1],val[maxn],zhu[maxn<<1],quan[maxn<<1],tail; 15 llg minl[maxn<<1],maxl[maxn<<1],ans3[maxn<<1]; 16 char s[maxn]; 17 18 struct SAM 19 { 20 struct 21 { 22 llg len,f,ch[SIZE]; 23 void init() 24 { 25 len=0,f=-1; 26 memset(ch,0xff,sizeof(ch)); 27 } 28 }e[maxn<<1]; 29 30 vector<llg>a[maxn<<1]; 31 llg idx,last,size[maxn<<1]; 32 33 void init(){idx=last=0; e[idx++].init(); memset(size,0,sizeof(size)); } 34 35 llg newnode(){e[idx].init(); return idx++;} 36 37 void insert(llg c) 38 { 39 llg end=newnode(),tmp=last; 40 e[end].len=e[last].len+1; size[end]=1; zhu[end]=1; quan[end]=val[tail]; maxl[end]=val[tail],minl[end]=val[tail]; tail++; 41 for (;tmp!=-1 && e[tmp].ch[c]==-1;tmp=e[tmp].f) 42 e[tmp].ch[c]=end; 43 if (tmp==-1) e[end].f=0; 44 else 45 { 46 llg nxt=e[tmp].ch[c]; 47 if (e[tmp].len+1==e[nxt].len) e[end].f=nxt; 48 else 49 { 50 llg np=newnode();// maxl[np]=maxl[end],minl[np]=minl[end]; 51 e[np]=e[nxt]; 52 e[np].len=e[tmp].len+1; 53 e[nxt].f=e[end].f=np; 54 for (;tmp!=-1 && e[tmp].ch[c]==nxt;tmp=e[tmp].f) {e[tmp].ch[c]=np;} 55 } 56 } 57 last=end; 58 // cout<<last<<endl; 59 } 60 61 void link_fa() {for (llg i=1;i<idx;i++) a[e[i].f].push_back(i);} 62 63 void dp(llg x) 64 { 65 llg w=a[x].size(),v; 66 for (llg i=0;i<w;i++) dp(a[x][i]); 67 for (llg i=0;i<w;i++) 68 { 69 v=a[x][i]; 70 ans1[e[x].len]+=size[x]*size[v]; 71 if (1) 72 { 73 if (maxl[v]!=-1*inf) 74 { 75 if (maxl[x]!=-1*inf) ans2[e[x].len]=max(ans2[e[x].len],maxl[x]*maxl[v]); 76 maxl[x]=max(maxl[x],maxl[v]); 77 } 78 if (minl[v]!=inf) 79 { 80 if (minl[x]!=inf) ans2[e[x].len]=max(ans2[e[x].len],minl[x]*minl[v]); 81 minl[x]=min(minl[x],minl[v]); 82 } 83 } 84 size[x]+=size[v]; 85 } 86 //ans1[e[x].len]+=size[x]; 87 } 88 }sam; 89 90 int main() 91 { 92 yyj("a"); 93 cin>>n; 94 sam.init(); 95 scanf("%s",s); 96 for (llg i=0;i<=n*2;i++) ans2[i]=maxl[i]=-1*inf,minl[i]=inf,ans3[i]=inf*-1; 97 for (llg i=0;i<n;i++) scanf("%lld",&val[i]); 98 for (llg i=0;i<(n+1)/2;i++) swap(val[i],val[n-i-1]); 99 for (llg i=n-1;i>=0;i--) 100 sam.insert(s[i]-'a'); 101 sam.link_fa(); 102 sam.dp(0); 103 for (llg i=n-1;i>=1;i--) 104 { 105 ans1[i-1]+=ans1[i]; 106 if (ans1[i]) ans2[i-1]=max(ans2[i-1],ans2[i]); 107 } 108 // for (llg i=0;i<n;i++) ans3[sam.e[i].len]=max(ans3[sam.e[i].len],ans2[i]); 109 for (llg i=0;i<n;i++) printf("%lld %lld ",ans1[i],ans1[i]?ans2[i]:0); 110 return 0; 111 }