字符集大小为1e9.............使用 map 吧
统计本质不同的子串个数是SAM的经典应用之一
本质不同的子串个数其实就是(sum max(x)-min(x)+1)
所以我们新建结点 (np) 时统计它的答案即可
根据我们统计的式子，显然新建节点(nq)的时候，不会对答案造成影响。
#include<cstdio>
#include<cstring>
#include<map>
typedef long long ll;
const int maxn = 2e5+20;
int par[maxn],mx[maxn],tr[maxn][26],Right[maxn],c[maxn],id[maxn];
char A[maxn>>1];
int tot=0;
std::map<int,int> M;
int cnt = 1,last = 1;
ll ans = 0;
void extend(int x) {
int np = ++cnt,p = last;
Right[np]=1;
mx[np]=mx[p]+1;
last=np;
while(p&&!tr[p][x]) tr[p][x]=np,p=par[p];
if(!p) par[np]=1;
else {
int q = tr[p][x];
if(mx[q]==mx[p]+1) {
par[np]=q;
}
else {
int nq = ++cnt;
mx[nq]=mx[p]+1;
memcpy(tr[nq],tr[q],sizeof tr[nq]);
par[nq]=par[q];
par[q]=par[np]=nq;
while(p&&tr[p][x]==q) tr[p][x]=nq,p=par[p];
}
}
ans+=mx[np]-mx[par[np]];
return;
}
int n,k,t;
inline void topsort() {
for(int i = 1;i<=cnt;++i) ++c[mx[i]];
for(int i = 1;i<=n;++i) mx[i]+=mx[i-1];
for(int i = 1;i<=cnt;++i) id[c[mx[i]]--]=i;
for(int i = cnt;i;--i) Right[par[id[i]]]+=Right[id[i]];
return;
}
int ch;
int main() {
scanf("%d",&n);
for(int i = 1;i<=n;++i) {
scanf("%d",&ch);
if(M[ch]==0) {
M[ch]=++tot;
}
extend(M[ch]);
printf("%lld
",ans);
}
return 0;
}