后缀数组

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int n,rk[N],sa[N];
string s;
int sum[N],x[N],y[N],m=255;
void GetSA(){
	//1.按照第一个字符基数排序
	for(int i=1;i<=n;i++)sum[x[i]=s[i]]++;
	for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
	for(int i=n;i>=1;i--)sa[sum[x[i]]--]=i;
	
	
	for(int k=1;k<=n;k<<=1){
		int num = 0;
		for(int i=n-k+1;i<=n;i++)y[++num] = i;
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num] = sa[i]-k;
		
		for(int i=1;i<=m;i++)sum[i] = 0;
		for(int i=1;i<=n;i++)sum[x[i]]++;
		for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
		for(int i=n;i>=1;i--)sa[sum[x[y[i]]]--] = y[i],y[i] = 0;
		
		swap(x,y);
		x[sa[1]] = 1;
		num = 1;
		
		for(int i=2;i<=n;i++){
			x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		}
		if(num==n)break;
		m=num;
	}
}
int main(){
	cin>>s;
	n = s.size();
	s = "#"+s;
	GetSA();
	for(int i=1;i<=n;i++){
		cout<<sa[i]<<" ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int n,rk[N],sa[N],k,old[N];
string s;
bool cmp(int x,int y){
	if(rk[x]!=rk[y])return rk[x]<rk[y];
	else return rk[x+k]<rk[y+k];
}
int main(){
	cin>>s;
	n = s.size();
	s="#"+s;
	for(int i=1;i<=n;i++){
		rk[i] = s[i];
		sa[i] = i;
	}
	for(k=1;k<n;k<<=1){
		sort(sa+1,sa+n+1,cmp);
		memcpy(old,rk,sizeof(rk));
		int num = 0;
		for(int i=1;i<=n;i++){
			if(old[sa[i]]==old[sa[i-1]] && old[sa[i]+k]==old[sa[i-1]+k])rk[sa[i]]=num;
			else rk[sa[i]] = ++num;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<sa[i]<<" ";
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int x[N],y[N],rk[N],sa[N],height[N],sum[N];
string s;
int n,m=256;
void GetSA(){
	for(int i=1;i<=n;i++)sum[x[i]=s[i]]++;
	for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
	for(int i=n;i>=1;i--)sa[sum[x[i]]--]=i;
	
	for(int k=1;k<=n;k<<=1){
		int num = 0;
		for(int i=n-k+1;i<=n;i++)y[++num] = i;
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num] = sa[i]-k;
		for(int i=1;i<=m;i++)sum[i]=0;
		for(int i=1;i<=n;i++)sum[x[i]]++;
		for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
		for(int i=n;i>=1;i--)sa[sum[x[y[i]]]--]=y[i],y[i]=0;
		swap(x,y);
		num = 1;
		x[sa[1]] = 1;
		for(int i=2;i<=n;i++){
			x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		}
		if(num==n)break;
		m = num;
	}
}
void GetHeight(){
	for(int i=1;i<=n;i++)rk[sa[i]] = i;
	int k = 0;
	for(int i=1;i<=n;i++){
		if(rk[i]==1)continue;
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]-1]+k])k++;
		height[rk[i]] = k;
	}
}
int main(){
	cin>>s;
	n =s.size();
	s = "#"+s;
	GetSA();
	GetHeight();
	for(int i=1;i<=n;i++){
		cout<<sa[i]-1<<" ";
	}
	cout<<endl;
	for(int i=1;i<=n;i++){
		cout<<height[i]<<" ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
#define int long long
int n,a[N],b[N],id[N];
string s;
int sa[N],rk[N],height[N];
int st[N][21];
int x[N],y[N],sum[N],m;
void GetSA(){
	for(int i=1;i<=n;i++)sum[x[i]=id[i]]++;
	for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
	for(int i=n;i>=1;i--)sa[sum[x[i]]--]=i;
	
	for(int k=1;k<=n;k<<=1){
		int num = 0;
		for(int i=n-k+1;i<=n;i++)y[++num] = i;
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
		for(int i=1;i<=m;i++)sum[i] = 0;
		for(int i=1;i<=n;i++)sum[x[i]]++;
		for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
		for(int i=n;i>=1;i--)sa[sum[x[y[i]]]--]=y[i],y[i]=0;
		swap(x,y);
		
		num = 1;
		x[sa[1]] = 1;
		for(int i=2;i<=n;i++){
			x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		}
		if(num==n)break;
		m = num;
	}
}
void GetHeight(){
	for(int i=1;i<=n;i++)rk[sa[i]] = i;
	int k = 0;
	for(int i=1;i<=n;i++){
		if(rk[i]==1)continue;
		if(k)k--;
		while(id[i+k]==id[sa[rk[i]-1]+k])k++;
		height[rk[i]] = k;
	}
}
void GetST(){
	for(int i=1;i<=n;i++){
		st[i][0] = height[i];
	}
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j] = min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
int GetMin(int x,int y){
	int t = log2(y-x+1);
	return min(st[x][t],st[y-(1<<t)+1][t]);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i] = a[i];
	}
	reverse(a+1,a+n+1);
	sort(b+1,b+n+1);
	int tot = unique(b+1,b+n+1)-b-1;
	m = tot;
	for(int i=1;i<=n;i++){
		id[i] = lower_bound(b+1,b+tot+1,a[i])-b;
	}
	GetSA();
	GetHeight();
	GetST();
	set<int>s;
	int res = 0;
	for(int i=n;i>=1;i--){
		s.insert(rk[i]);
		auto it = s.find(rk[i]);
		int k = 0;
		if(it!=s.begin()){
			auto p = *(--it);
			k = GetMin(p+1,rk[i]);
			++it;
		}
		++it;
		if(it!=s.end()){
			auto p = *it;
			k = max(k,GetMin(rk[i]+1,p));
		}
		res+=n-i+1-k;
		cout<<res<<endl;
	}
	return 0;
}