阿巴阿巴 不知道咋解释 vector

#include<bits/stdc++.h>
using namespace std;

vector<int> memory[2000005];
vector<int> v1[1100005];
vector<int> RadixSort(int sp, int n)
{
if(!memory[sp].empty()){return memory[sp];}
vector<int>rank = RadixSort(sp/2, n);
vector<int>tmp = RadixSort(sp-sp/2, n);
vector<int>tp(n);
for(int i=0;i<n;i++) tp[i] = (i+(sp/2)<n ? tmp[i+sp/2] : tmp[i+sp/2-n]);
vector<int> v(n);
for(int i=0;i<n;i++) v[i]=i;
auto reorder = [&](vector<int>& a){
int tot = max(100, n+1);
for(int i=1;i<=tot;i++) v1[i].clear();
for(auto it:v)
v1[a[it]].push_back(it);
v.clear();
for(int i=0;i<tot;i++) for(auto it:v1[i]) v.push_back(it);
};
reorder(tp);
reorder(rank);
auto pre = make_pair(-1, -1);
int cnt = 0, t=0;
for(auto it:v)
{
if(pre.first != rank[it] || pre.second != tp[it]) {cnt++;cnt+=t;t=0;}
else t++;
pre = make_pair(rank[it], tp[it]);
rank[it] = cnt;
}
memory[sp] = rank;
return rank;
}
void suffix_sort(string &s)
{
int n = s.length();
vector<int> rank(n), tp(n);
for(int i=0;i<n;i++) rank[i] = s[i] - '0' + 1;
memory[1] = rank;
RadixSort(n,n);
}
int main()
{
string s;
cin>>s;
int n = s.length();
suffix_sort(s);
auto& ans = memory[n];
for(int i=0;i<n;i++) cout<<ans[i] - 1<<" ";
return 0;
}

100pts:
这个暴力就能做,方法很多。

200pts:
如果你恰巧学过后缀排序，这题可以直接套上去。
后缀数组求的是长为\(1,2,4...,\)的后缀的排名。这里 \(2^{20}\) 是 \(2\) 的幂次。将字符串复制成两倍，然后输出\(s[0],s[1],....s[n]\)开头的长度为n的后缀的排名即可。

300pts:
本题应运用分治法，最终是要求长为n的排名，则将n分成两部分\(n=n_1+n_2\)，便求得了长为\(n_1\)，\(n_2\)的排名，然后采用基数排序方法将两部分答案合并即可（以s[i]的长为\(n_1\)的排名为第一关键字，s[i+\(n_1\)]的长为\(n_2\)的排名为第二关键字排序）。一轮基数排序是 \(O(n)\)，一共有 \(O(\log n)\) 轮，所以时间复杂度是\(O(n \log n)\)

不知道如果用sort代替基数排序能否过这题?

代码写的有点乱...

Code:

#include<bits/stdc++.h>
using namespace std;

vector<int> memory[2000005];
vector<int> v1[1100005];
vector<int> RadixSort(int sp, int n)
{
    if(!memory[sp].empty()){return memory[sp];}
    vector<int>rank = RadixSort(sp/2, n);//第一关键字
    vector<int>tmp = RadixSort(sp-sp/2, n);
    vector<int>tp(n); //第二关键字
    for(int i=0;i<n;i++) tp[i] = (i+(sp/2)<n ? tmp[i+sp/2] : tmp[i+sp/2-n]); 
    vector<int> v(n);//原顺序
    for(int i=0;i<n;i++) v[i]=i;
    auto reorder = [&](vector<int>& a){
        int tot = max(100, n+1);
        for(int i=1;i<=tot;i++) v1[i].clear();
        for(auto it:v) 
            v1[a[it]].push_back(it);
        v.clear();
        for(int i=0;i<tot;i++) for(auto it:v1[i]) v.push_back(it); 
    };
    reorder(tp);
    reorder(rank);
    auto pre = make_pair(-1, -1);
    int cnt = 0, t=0;
    for(auto it:v)
    {
        if(pre.first != rank[it] || pre.second != tp[it]) {cnt++;cnt+=t;t=0;}
        else t++;
        pre = make_pair(rank[it], tp[it]);
        rank[it] = cnt;
    }
    memory[sp] = rank;
    return rank; 
}
void suffix_sort(string &s)
{
    int n = s.length();
    vector<int> rank(n), tp(n);
    for(int i=0;i<n;i++) rank[i] = s[i] - '0' + 1;
    memory[1] = rank; 
    RadixSort(n,n);
}
int main()
{
    string s; 
    cin>>s;
    int n = s.length();
    suffix_sort(s);
    auto& ans = memory[n];
    for(int i=0;i<n;i++) cout<<ans[i] - 1<<" "; 
    return 0;
}