求助 SA 84pts WA on #9 #10

/*
	Luogu name: Symbolize
	Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int scnt,id[N],len[N],ans[N],a[N],w=1;
int n,sa[N],rk[N],tmp[N],cnt[N],idx,ht[N],Max,f[N][25];
char t[N];
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
char s[N];
void radix_sort(int k)
{
	idx=0;
	rep1(i,n-k+1,n) tmp[++idx]=i;
	rep1(i,1,n) if(sa[i]>k) tmp[++idx]=sa[i]-k;
	rep1(i,1,Max) cnt[i]=0;
	rep1(i,1,n) ++cnt[rk[i]];
	rep1(i,2,Max) cnt[i]+=cnt[i-1];
	rep2(i,n,1) if(cnt[rk[tmp[i]]]>0) sa[cnt[rk[tmp[i]]]--]=tmp[i];
	swap(rk,tmp);
	return;
}
bool cmp(int x,int y){return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];}
void get_sa()
{
	Max=1000;
	memset(cnt,0,sizeof cnt);
	memset(sa,0,sizeof sa);
	memset(rk,0,sizeof rk);
	memset(ht,0,sizeof ht);
	memset(tmp,0,sizeof tmp);
	rep1(i,1,n) sa[i]=i,rk[i]=s[i];
	w=1;
	while(w<n)
	{
		sort(sa+1,sa+n+1,cmp);
		memcpy(tmp,rk,sizeof rk);
		int id=0;
		rep1(i,1,n)
		{
			if(tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+w]==tmp[sa[i-1]+w]) rk[sa[i]]=id;
			else rk[sa[i]]=++id;
		}
		if(id==n) break;
		w<<=1;
	}
	return;
}
void get_ht()
{
	int k=0;
	rep1(i,1,n)
	{
		if(k) --k;
		while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
		ht[rk[i]]=k;
	}
	return;
}
void build_st()
{
	memset(f,0,sizeof f);
	rep1(i,1,n) f[i][0]=ht[i];
	rep1(j,1,20) rep1(i,1,n-(1<<j)+1) f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	return;
}
int query(int l,int r)
{
	if(l>r) swap(l,r);
	++l;
	int k=log2(r-l+1);
	return min(f[l][k],f[r-(1<<k)+1][k]);
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scnt=read();
	rep1(i,1,scnt)
	{
		cin>>t+1;
		len[i]=strlen(t+1);
		rep1(j,1,len[i])
		{
			s[++n]=t[j];
			id[n]=i;
		}
		s[++n]='z'+i;
		ans[i]=len[i]*(len[i]+1)/2;
	}
	get_sa();
	get_ht();
	build_st();
	int now=0;
	rep2(i,n,1)
	{
		if(id[sa[i]]!=id[sa[i+1]]) now=i+1;
		if(now>i) a[i]=query(i,now);
	}
	rep1(i,1,n) ans[id[sa[i]]]-=max(a[i],ht[i]);
	rep1(i,1,scnt) cout<<ans[i]<<endl;
	return 0;
}