这个是我本题代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int rk[1000006]; 
int x[1000006],y[1000006],xx[1000006];
int cnt[1000006],id[1000006],sa[1000006];
int vis[128];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>s;
	int n=s.size();
	s='$'+s;
	vector<char>z;
	for(int i=1;i<=n;i++){
        if(!vis[s[i]])z.push_back(s[i]);
		vis[s[i]]=1;
	}
	sort(z.begin(),z.end());
	for(int i=1;i<=n;i++){
		rk[i]=lower_bound(z.begin(),z.end(),s[i])-z.begin()+1;
	}
    for(int i=1;i<=n;i++)sa[i]=i;
    sort(sa+1,sa+1+n,[&](int a,int b){
        return rk[a]<rk[b];
    });
	int s=0;
	for(int f=0;(1ll<<f)<=n;f++){
        int pos=0;
        for(int i=n-(1ll<<f)+1;i<=n;i++){
            id[++pos]=i;
        }
        for(int i=1;i<=n;i++){
            if(sa[i]>1ll<<f){
                id[++pos]=sa[i]-(1ll<<f);
            }
        }
        for(int i=1;i<=n;i++){
            xx[i]=rk[id[i]];
            x[i]=rk[i];
            if(i+(1ll<<f)<=n)y[i]=rk[i+(1ll<<f)];
        }
		for(int i=0;i<=n;i++){
			cnt[i]=0;
		}
		for(int i=1;i<=n;i++){
			cnt[xx[i]]++;
		}
		for(int i=1;i<=n;i++){
			cnt[i]+=cnt[i-1];
		}
		for(int i=n;i>=1;i--){
			sa[cnt[xx[i]]--]=id[i];
		}
		int num=0;
        for(int i=1;i<=n;i++){
			if(i==1||x[sa[i]]!=x[sa[i-1]]||y[sa[i]]!=y[sa[i-1]])num++;
			rk[sa[i]]=num;
		}
	}
	for(int i=1;i<=n;i++)cout<<sa[i]<<' ';
	return 0;
}

测试过了题解的几篇代码（显然要是 $O(n\log n)$ 的），在每个测试点不超过 120ms，而我的差不多要 750ms了。经过测试瓶颈在这里：

for(int i=n;i>=1;i--){
    sa[cnt[xx[i]]--]=id[i];
}

这里差不多 360ms。

但是看到其他代码也存在这行（或者类似），想知道为啥。