题解 P5353 【【XR-1】树上后缀排序】

· · 题解

后缀平衡树

很多人说它是在线的后缀数组，其实我感觉它的功能不止于此。

前置知识

替罪羊树

原理

后缀平衡树是一个以字典序为关键字的有序字符串集X，它可以资瓷两种复杂度为O(\log n)的操作：

所以，如果对一个字符串逆序执行插入操作，它就是严格的“后缀平衡树”，它的中序遍历也就是后缀数组。但其实上，观察这两个操作，它完全可以维护一个有根树森林。

实现

两种插入操作完全可以视为一种。我们考虑要加入一个字符串xS，我们要做的就是从根开始与当前节点进行比较，然后进入左/右儿子，直到找到一个空位为止。现在的问题就是，如何比较要插入的字符串和节点上的字符串。

显然我们不能O(n)暴力比较。考虑到要插入的字符串xS，除去第一个字母之后的S已经在树中，并且树是有序的。那么当第一个字符相同时，我们完全可以利用这棵树进行O(\log n)比较后面的部分，这样的话，插入操作时O(\log ^ 2 n)的。

考虑如何进行O(1)比较，来做到单次操作是O(\log n)。我们对于每个节点维护一个key值代表在树中的相对位置。具体方法是：选取一个很大的值域，每次进入下一层时根据左右儿子将值域折半，最终节点的值就是当前值域的mid值。当需要比较两个已经在树中的字符串时，直接比较key值即可，复杂度O(1)。

对于如何维护平衡，最简单的方法就是使用替罪羊树，注意在重构时要重新赋key值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 1e6 + 5;
const double LIM = 1e16;
const float Alpha = 0.7;

int n;
char S[MAXN];
int fa[MAXN];
int rk[MAXN], sa[MAXN];

namespace SufTree{
    double val[MAXN];
    int siz[MAXN];
    int ch[MAXN][2];
    int tr[MAXN], cnt;
    int rt;

    void Update(int x) {
        siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];
    }

    int Bad(int x) {
        return 1.0 * siz[ch[x][0]] > Alpha * siz[x] || 1.0 * siz[ch[x][1]] > Alpha * siz[x];
    }

    int Comp(int x, int y) {
        return S[x] < S[y] || (S[x] == S[y] && val[fa[x]] < val[fa[y]]);
    }

    void Pia(int x) {
        if (!x) return;
        Pia(ch[x][0]);
        tr[++cnt] = x;
        Pia(ch[x][1]);
        ch[x][0] = ch[x][1] = 0;
    }

    void Rebuild(int &x, int l, int r, double lv, double rv) {
        if (l > r) return;
        int mid = (l + r) >> 1;
        double midv = (lv + rv) / 2;
        x = tr[mid];
        val[x] = midv;
        Rebuild(ch[x][0], l, mid - 1, lv, midv);
        Rebuild(ch[x][1], mid + 1, r, midv, rv);
        Update(x);
    }

    void Maintain(int &x, double lv, double rv) {
        if (Bad(x)) {
//          cerr << "*" << x;
            cnt = 0;
            Pia(x);
            Rebuild(x, 1, cnt, lv, rv);
        }
    }

    void Insert(int &x, int idx, double lv, double rv) {
        if (!x) {
            x = idx;
            siz[x] = 1;
            ch[x][0] = ch[x][1] = 0;
            val[x] = (lv + rv) / 2;
            return;
        }
        if (Comp(idx, x)) Insert(ch[x][0], idx, lv, val[x]);
        else Insert(ch[x][1], idx, val[x], rv);
        Update(x);
        Maintain(x, lv, rv);
    }

    void Calc(int x) {
        if (!x) return;
        Calc(ch[x][0]);
        sa[++cnt] = x;
        Calc(ch[x][1]);
    }

    void Build() {
        for (int i = 1; i <= n; i++) {
            Insert(rt, i, 1, LIM);
        }
        cnt = 0;
        Calc(rt);
        for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) scanf("%d", fa + i);
    scanf("%s", S + 1);
    SufTree::Build();
    for (int i = 1; i <= n; i++) printf("%d ", sa[i]);
    return 0;
}
/*
10 5
S 0
Y 1
R 2
E 3
N 4
E 5
A 6
D 7
Y 7
R 9
RY
E
N
S
AY
*/