经过一个小时的卡常以后成功的在使用 vector 的情况下没有 TLE

但是 MLE 了QAQ

所以 vector 在 clear 以后不会重新算内存么QAQ

#include <bits/stdc++.h>
#define ll long long
#define Mid ((L+R)>>1)
using namespace std;
typedef pair<int,int> pii;
inline int read(){
	char c;int x=0;int b=1;do{c=getchar();if(c==45)b=-1;}while(c>57||c<48);
	do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);x*=b;return x;
}
const int maxn=1000010;
int a[maxn],s[maxn][2],tmp[maxn][3],w[maxn];
vector<int>t[maxn];
string S;
int tmp2[maxn][2];
map<char,int>M;
int main() {
	register int i,j,k,n,m,cnt=0,Mx;
	freopen("P3809.in","r",stdin);
	freopen("P3809.out","w",stdout);
	for(i='0';i<='9';i++)M[i]=++cnt;
	for(i='A';i<='Z';i++)M[i]=++cnt;
	for(i='a';i<='z';i++)M[i]=++cnt;
	getline(cin,S);n=S.size();
	for(i=1;i<=n;i++){a[i]=s[i][0]=M[S[i-1]];}
	for(int l=1;cnt!=n;l<<=1){
		cnt=Mx=0;
		for(i=1;i<=n;++i){
			if(i+l<=n)s[i][1]=s[i+l][0];
			else s[i][1]=0;
			t[s[i][1]].push_back(i);
			Mx=max(Mx,s[i][0]);
		}
		for(i=0;i<=Mx;++i){
			int len=t[i].size();
			for(j=0;j<len;++j){
				int now=t[i][j];
				w[++cnt]=now;
			}
			t[i].clear();
		}
		for(i=1;i<=n;++i){
			tmp[i][0]=s[w[i]][0];tmp[i][1]=s[w[i]][1];tmp[i][2]=w[i];
			t[tmp[i][0]].push_back(i);
		}
		cnt=0;
		for(i=0;i<=Mx;++i){
			int len=t[i].size();
			for(j=0;j<len;++j){
				int now=t[i][j];
				w[++cnt]=now;
			}
			t[i].clear();
		}
		for(i=1;i<=n;i++)tmp2[i][0]=tmp[w[i]][0],tmp2[i][1]=tmp[w[i]][1];
/*
		for(i=1;i<=n;i++)cout<<tmp2[i][0]<<' '<<tmp2[i][1]<<' '<<tmp2[i][2]<<endl;cout<<endl;
*/
		cnt=0;
		for(i=1;i<=n;++i){
			if(tmp2[i][0]^tmp2[i-1][0] || tmp2[i][1]^tmp2[i-1][1])++cnt;
			tmp[i][0]=cnt;
		}
		for(i=1;i<=n;++i)s[tmp[w[i]][2]][0]=tmp[i][0];
	}
	memset(tmp,0,sizeof(tmp));
	for(i=1;i<=n;i++)tmp[s[i][0]][0]=i;
	for(i=1;i<=n;i++)printf("%d ",tmp[i][0]);
	cout<<endl;
	//cerr << 1.0*clock()/CLOCKS_PER_SEC << endl;
	return 0;
}