后缀排序

做了 ABC270F，茅塞顿开。后缀排序，分明是抄的循环移位排序板子。

ABC270F

题意：给定两个长度为 \(n\) 的字符串 \(s,t\)，求有多少个有序点对 \((i,j)\) 使得 \((s \rightarrow i) < (t \rightarrow j)\)。其中 \((s \rightarrow i)\) 表示 \(s\) 向右循环位移 \(i\) 位。其中 \(i,j \in [0,n-1]\)。

\(n \le 2 \times 10^5\)

分析：首先转化题意。将所有循环移位之后的字符串混在一起排序，所需要寻找的就是 \(rank_{(s\rightarrow i)} \le rank_{(t\rightarrow j)}\) 的个数。也就是说，混排找到 \(rank\) 就完事了。

其实后缀排序抄的循环移位排序板子。循环移位是本质。

思想就是要利用好“循环”的性质：以 \(c_i\) 开头，长度为 \(2^k\) 的字符串的后半部分也就是以 \(c_{i + 2^{k-1}}\) 开头，长度为 \(2^{k-1}\) 的字符串。

定义“第 \(i\) 层”为排好以每个位置为开头， \(2^i\) 为长度的字符串。这时我们就可以利用上一层求出的 rank，求出这一层一个 pair，也就是左半边和右半边的 rank，其中右半边的 rank 是从别的地方拿来的（合理利用信息）。

注意并不一定是 \(n=2^k\) 的才可以排序，我们最后一次排序可以类似 ST 表，有一定的重合，比如 \(n=6\)，那么我们使用 \(1234~3456\) 作为上一层的 pair 的来源。可以证明这个是对的。（怎么证明：考虑讨论两个字符串中是第几位存在大小不一样的关系，然后分别看看能不能检验出来）

然后算答案，有可能会踩坑（atcoder 的数据水的要命，踩坑了也能过几十个点）。正确的做法是，先把 \(s\) 里所有 rnk 拍到桶里做前缀和，然后用 \(t\) 里的元素去找。

赛时写的是没有优化的 \(O(n \log^2 n)\) 算法。如果用基数排序可以做到 \(O(n \log n)\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
int n; 
int rnk[500010];
int pow2[500010];
vector<pair<char, int>> init;
vector<pair<pair<int, int>, int>> pk;  //后缀排序用的
int calc(int i, int len) {return (i<n ? (i+len)%n : n+((i-n+len)%n));}
int cc[500010];
int ss[500010];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    cin >> n;
  //  cout << calc(4, 2);
    pow2[0]=1;
    f(i,1,n)pow2[i]=pow2[i-1]*2;
    string s,t;cin>>s>>t;
    s += t;
    int x = log2(n);
    //重新标号，从 0~n-1,n~2n-1
    //len=1
    f(i,0,2*n-1){
        init.push_back({s[i],i});
    }
    sort(init.begin(),init.end());
    int now=0;
    f(i,0,2*n-1){
        if(i != 0 && init[i].first == init[i-1].first) rnk[init[i].second]=rnk[init[i-1].second];
        else rnk[init[i].second]=++now;
    }
  //  cout << "k=0"<<endl;
 //   f(i,0,2*n-1)cout<<rnk[i]<<" \n"[i==2*n-1];
    f(k, 0, x - 1){
        //排序长度为2^k
        int len=pow2[k];
      //  cout << len << endl;
        f(i,0,2*n-1){
            pk.push_back({{rnk[i],rnk[(i<n ? (i+len)%n : n+((i-n+len)%n))]}, i});
        }
        sort(pk.begin(),pk.end());
        now=0;
        f(i,0,2*n-1){
            if(i!=0&&pk[i].first==pk[i-1].first) rnk[pk[i].second]=rnk[pk[i-1].second];
            else rnk[pk[i].second]=++now;
        }
        pk.clear();
       // cout << "k="<<k<<endl;
      //  f(i,0,2*n-1)cout<<rnk[i]<<" \n"[i==2*n-1];
    }
    int lft = n - pow2[x];
    f(i,0,2*n-1){
        pk.push_back({{rnk[i],rnk[(i<n ? (i+lft)%n : n+((i-n+lft)%n))]}, i});
    }    
    sort(pk.begin(),pk.end());
    now=0;
    f(i,0,2*n-1){
        if(i!=0&&pk[i].first==pk[i-1].first) rnk[pk[i].second]=rnk[pk[i-1].second];
        else rnk[pk[i].second]=++now;
    }
    f(i,0,n-1)cc[rnk[i]]++;
   // f(i, 0, 2*n-1) cout<<rnk[i]<<" \n"[i==2*n-1];
   // cout<<now<<endl;
    f(i, 1, now) ss[i] = ss[i-1]+cc[i];
    int ans=0;
    f(i, n,2*n-1)ans+=ss[rnk[i]];
    cout<<ans<<endl;
    time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}

后缀排序

后缀排序为什么抄的循环节排序？

考虑后缀和循环的差别是什么。后缀结束了就不会有下一个了，于是例如 \(ab\) 和 \(a\) 比较的时候因为 \(a\) 的第二位没有了，所以直接判定 \(a\) 比较小。这一点如果用循环移位在 \(a\) 之后加上个什么东西可就两说了。

所以我们为了能够统一每个字符串的长度，在每个后缀结束的时候加上一个 \(\$\) 符号，表示一个比所有字母都小的符号。然后把后面的循环补上来，可以发现最终排序的就是一堆循环移位字符串。