(做题纪要前放点闲话应该没啥问题...吧?)
禾念你虽然pv里的藏文格式全都错了但是应该不至于直接把藏文全删了吧(
还有天依游学记怎么这么快就还剩十几天就要完结了，哭哭
哎我游学记的谷子怎么还不到
P2408 不同子串个数
板子题，最后结果为 \(\dfrac{n(n-1)}{2}-\sum\limits_{i=2}^{n}\text h_i\)
这个我应该在学习笔记里写了，这里挂一下
代码
点击查看代码
namespace solve{
int height[N],sa[N],oldsa[N],rk[N],oldrk[N],cnt[N],key[N];
namespace SA{
inline bool cmp(int x,int y,int w){
return (oldrk[x]==oldrk[y])&&(oldrk[x+w]==oldrk[y+w]);
}
inline void Init(char *s){
int n=strlen(s+1),m=127,tot;
for_(i,1,n)
rk[i]=s[i],
++cnt[rk[i]];
for_(i,1,m)
cnt[i]+=cnt[i-1];
_for(i,n,1) sa[cnt[rk[i]]--]=i;
for(int w=1;;w<<=1,m=tot) {
tot=0;
_for(i,n,n-w+1)
oldsa[++tot]=i;
for_(i,1,n)
if(sa[i]>w)
oldsa[++tot]=sa[i]-w;
memset(cnt,0,sizeof(cnt));
for_(i,1,n)
++cnt[key[i]=rk[oldsa[i]]];
for_(i,1,m)
cnt[i]+=cnt[i-1];
_for(i,n,1)
sa[cnt[key[i]]--]=oldsa[i];
memcpy(oldrk+1,rk+1,n*sizeof(int));
tot=0;
for_(i,1,n)
rk[sa[i]]=((cmp(sa[i],sa[i-1],w))?(tot):(++tot));
if(tot==n)
break;
}
}
inline void Init_H(char *s){
int n=strlen(s+1),tot=0;
for_(i,1,n){
if(!rk[i]) continue;
if(tot) --tot;
while(s[i+tot]==s[sa[rk[i]-1]+tot]) ++tot;
height[rk[i]]=tot;
}
}
}
using namespace SA;
inline void In(){
int n,ans=0;
char s[N];
FastI>>n>>(s+1);
Init(s);Init_H(s);
for_(i,2,n) ans+=height[i];
FastO<<((n*(n+1)/2)-ans)<<endl;
}
}
using namespace solve;
P3181 「HAOI2016」找相同字符
大到小扫描 \(height\) 数组，合并相邻后缀
当前块中的贡献就是第一个串的后缀数 $\times $ 第二个串的后缀数 \(\times\) 当前枚举的height。
用并查集维护即可
代码
点击查看代码
namespace solve{
int height[N],sa[N],oldsa[N],rk[N],oldrk[N],cnt[N],key[N];
namespace SA{
inline bool cmp(int x,int y,int w){
return (oldrk[x]==oldrk[y])&&(oldrk[x+w]==oldrk[y+w]);
}
inline void Init(char *s){
int n=strlen(s+1),m=127,tot;
for_(i,1,n)
rk[i]=s[i],
++cnt[rk[i]];
for_(i,1,m)
cnt[i]+=cnt[i-1];
_for(i,n,1) sa[cnt[rk[i]]--]=i;
for(int w=1;;w<<=1,m=tot) {
tot=0;
_for(i,n,n-w+1)
oldsa[++tot]=i;
for_(i,1,n)
if(sa[i]>w)
oldsa[++tot]=sa[i]-w;
memset(cnt,0,sizeof(cnt));
for_(i,1,n)
++cnt[key[i]=rk[oldsa[i]]];
for_(i,1,m)
cnt[i]+=cnt[i-1];
_for(i,n,1)
sa[cnt[key[i]]--]=oldsa[i];
memcpy(oldrk+1,rk+1,n*sizeof(int));
tot=0;
for_(i,1,n)
rk[sa[i]]=((cmp(sa[i],sa[i-1],w))?(tot):(++tot));
if(tot==n)
break;
}
}
inline void Init_H(char *s){
int n=strlen(s+1),tot=0;
for_(i,1,n){
if(!rk[i]) continue;
if(tot) --tot;
while(s[i+tot]==s[sa[rk[i]-1]+tot]) ++tot;
height[rk[i]]=tot;
}
}
}
using namespace SA;
int f[N],g[N],A[N],B[N];
inline bool cmp1(int a,int b){
return height[a]>height[b];
}
inline int find(int x){
return f[x]=((f[x]!=x)?find(f[x]):x);
}
char s1[N],s2[N],s[N];
inline void In(){
FastI>>(s1+1)>>(s2+1);
int len1=strlen(s1+1);
int len2=strlen(s2+1);
int n=len1+len2+1;
for_(i,1,n){
if(i==len1+1) s[i]='#';
else if(i<=len1) s[i]=s1[i];
else s[i]=s2[i-len1-1];
}
Init(s);Init_H(s);
for_(i,1,n){
g[i]=i+1;f[i]=i;
if(sa[i]>len1+1) B[i]=1;
if(sa[i]<=len1) A[i]=1;
}
sort(g+1,g+1+n,cmp1);
int ans=0;
for_(i,1,n-1){
int x=find(g[i]),y=find(g[i]-1);
ans+=(A[x]*B[y]+A[y]*B[x])*height[g[i]];
A[y]+=A[x];B[y]+=B[x];
f[x]=y;
}
write(ans);
}
}