「LOJ 6198」谢特

    「LOJ 6198」谢特

    LOJ 6198

    给出一个长度为 nn 仅包含小写字符的字符串 ss。

    定义后缀 ii 的权值为 wiw_i,定义两个不同后缀 i,j(i≠j)i, j(i \neq j) 的贡献为 LCP(i,j)+(wixor⁡wj)\mathrm{LCP}(i, j) + (w_i \operatorname{xor} w_j)。其中 LCP(i,j)\mathrm{LCP}(i, j) 表示后缀 ii 和后缀 jj 的最长公共前缀长度。

    你需要求出任意两个不同后缀 i,j(i≠j)i, j(i \neq j) 的贡献最大值。

    数据范围:1≤n≤1051 \leq n \leq 10^5,0≤wi<n0 \leq w_i < n。

    时空限制:11s / 512512MiB。

    Solution

    对于 LCP\mathrm{LCP} 问题,有一个观点:

    • 若使用 SA,就是将字符串问题转化成了序列问题(height 数组)。
    • 若使用 SAM,就是将字符串问题转化成了树上问题(parent 树)。

    本题的结构相当广泛。许多题目都是类似的:使用 “height 数组” 或 “parent 树” 确定一个 LCP\mathrm{LCP} 大小,然后启发式合并处理二元关系。

    SA 需要用 ST 表或笛卡尔树处理 height 数组,注意这里的笛卡尔树只需要处理 2∼n2 \sim n,计算答案的时候左端点需要减一;而 SAM 有个好处就是不用写 ST 表或笛卡尔树。

    算法一:SA + 可持久化 0/1 trie

    对字符串 ss 做一遍 SA,将 height 数组求出。

    定义排名为 ii 的后缀权值为 wi′w'_i = wSAiw_{\mathrm{SA}_i},故排名为 i,j(i≠j)i, j(i \neq j) 的后缀的贡献为

    min⁡i<k≤j{heightk}+(wi′xor⁡wj′)\min\limits_{i < k \leq j} \{ \mathrm{height}_k \} + \left( w'_i \operatorname{xor} w'_j \right)

    考虑最值分治。定义分治函数 solve(l,r)\mathrm{solve}(l, r) 表示计算 l≤i<j≤rl \leq i < j \leq r 情况下的答案。

    取分治重心 pp 为区间 (l,r](l, r] 中 height\mathrm{height} 值最小的位置(使用 ST 表或笛卡尔树求出)。先考虑计算 l≤i<p≤j≤rl \leq i < p \leq j \leq r 情况下的答案,随后调用 solve(l,p−1),solve(p,r)\mathrm{solve}(l, p - 1), \mathrm{solve}(p, r) 即可。

    此时 min⁡i<k≤j{heightk}=heightp\min\limits_{i < k \leq j} \{ \mathrm{height}_k \} = \mathrm{height}_p,故只需考虑 wi′xor⁡wj′w'_i \operatorname{xor} w'_j 的最大值。对于分治重心分出来的两个区间 [l,p−1],[p,r][l, p - 1], [p, r],我们选择长度较小的一段区间,穷举该区间里的每一个点,使用可持久化 0/1 trie 求出该点与另一段区间的异或最大值。

    倒过来看这个过程,每次枚举一个区间,总区间长度就至少乘二,这本质上是一个启发式合并(故称作启发式分裂)。

    时间复杂度 O(nlog⁡2n)O(n \log^2 n)。

    #include <bits/stdc++.h>
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    const int N = 100100;
    
    int n;
    std::string str;
    
    int w[N];
    
    int root[N];
    namespace trie {
        int NodeCount;
        struct node {
            int trans[2];
            int cnt;
        } t[N * 32];
    
        void init() {
            NodeCount = 0;
        }
    
        void insert(int &p, int q, int d, int x) {
            p = ++ NodeCount, t[p] = t[q], t[p].cnt ++;
            if (d < 0) return;
            int v = x >> d & 1;
            insert(t[p].trans[v], t[q].trans[v], d - 1, x);
        }
    
        int ask(int p, int q, int d, int x) {
            if (d < 0) return 0;
            int v = x >> d & 1;
            if (t[t[q].trans[v ^ 1]].cnt - t[t[p].trans[v ^ 1]].cnt) {
                return ask(t[p].trans[v ^ 1], t[q].trans[v ^ 1], d - 1, x) + (1 << d);
            } else {
                return ask(t[p].trans[v], t[q].trans[v], d - 1, x);
            }
        }
        int ask(int l, int r, int x) {
            return ask(root[l - 1], root[r], 16, x);
        }
    }
    
    int ans;
    
    namespace SA {
        int m;
        int sa[N], rk[N], height[N];
        int cnt[N], id[N], px[N];
        int tmprk[N * 2];
    
        int same(int x, int y, int k) {
            return tmprk[x] == tmprk[y] && tmprk[x + k] == tmprk[y + k];
        }
    
        void build() {
            if (n == 1) { sa[1] = rk[1] = 1, height[1] = 0; return; }
    
            for (int i = n + 1; i <= 2 * n; i ++) tmprk[i] = -1;
    
            m = 256;
            for (int i = 1; i <= n; i ++) rk[i] = str[i];
    
            for (int i = 1; i <= m; i ++) cnt[i] = 0;
            for (int i = 1; i <= n; i ++) cnt[rk[i]] ++;
            for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
            for (int i = n; i >= 1; i --) sa[cnt[rk[i]] --] = i;
    
            for (int k = 1, p = 0; k < n; k <<= 1, m = p) {
                p = 0;
                for (int i = n - k + 1; i <= n; i ++) id[++ p] = i;
                for (int i = 1; i <= n; i ++)
                    if (sa[i] > k) id[++ p] = sa[i] - k;
                
                for (int i = 1; i <= m; i ++) cnt[i] = 0;
                for (int i = 1; i <= n; i ++) cnt[px[i] = rk[id[i]]] ++;
                for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
                for (int i = n; i >= 1; i --) sa[cnt[px[i]] --] = id[i];
    
                for (int i = 1; i <= n; i ++) tmprk[i] = rk[i];
    
                p = 0;
                for (int i = 1; i <= n; i ++) rk[sa[i]] = same(sa[i - 1], sa[i], k) ? p : ++ p;
    
                if (p == n) break;
            }
    
            for (int i = 1, h = 0; i <= n; i ++) {
                if (h) h --;
                while (str[i + h] == str[sa[rk[i] - 1] + h]) h ++;
                height[rk[i]] = h;
            }
        }
    
        int rt;
        struct node {
            int lc, rc;
            int L, R;
        } t[N];
    
        int top, stk[N];
        void build_tree() {
            top = 0;
            for (int i = 2; i <= n; i ++) {
                t[i].lc = t[i].rc = 0, t[i].L = t[i].R = i;
            }
    
            for (int i = 2; i <= n; i ++) {
                int k = top;
                while (k && height[stk[k]] > height[i]) k --;
    
                if (k) t[stk[k]].rc = i;
                if (k < top) t[i].lc = stk[k + 1];
    
                stk[top = k + 1] = i;
            }
            rt = stk[1];
        }
    
        void solve(int p) {
            if (t[p].lc) solve(t[p].lc), chmin(t[p].L, t[t[p].lc].L);
            if (t[p].rc) solve(t[p].rc), chmax(t[p].R, t[t[p].rc].R);
    
            int l = t[p].L - 1, r = t[p].R;
    
            if (p - l < r - p + 1) {
                for (int i = l; i < p; i ++) {
                    chmax(ans, height[p] + trie::ask(p, r, w[sa[i]]));
                }
            } else {
                for (int i = p; i <= r; i ++) {
                    chmax(ans, height[p] + trie::ask(l, p - 1, w[sa[i]]));
                }
            }
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n;
        std::cin >> str, str = " " + str;
    
        for (int i = 1; i <= n; i ++) {
            std::cin >> w[i];
        }
    
        SA::build();
    
        trie::init();
        for (int i = 1; i <= n; i ++) {
            trie::insert(root[i], root[i - 1], 16, w[SA::sa[i]]);
        }
    
        SA::build_tree();
    
        ans = 0;
        SA::solve(SA::rt);
    
        std::cout << ans << '\n';
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/

    算法二:SAM + 0/1 trie 合并

    对字符串 ss 的反串建出 SAM,并求出 parent 树。

    设后缀 ii 在反串建出的 SAM 上的代表节点为 eie_i,则 LCP(i,j)\mathrm{LCP}(i, j) 等于 parent 树上 LCA(ei,ej)\mathrm{LCA}(e_i, e_j) 的 maxl。

    考虑遍历 parent 树。设当前节点为 uu,我们要计算两个后缀 i,ji, j 代表节点的 LCA\mathrm{LCA} 等于 uu 时的贡献。

    依次遍历 uu 的所有儿子 vv,考虑计算后缀 ii 来自子树 uu,后缀 jj 来自子树 vv 情况下的贡献。此时 LCP(i,j)=maxlu\mathrm{LCP}(i, j) = \mathrm{maxl}_u,故只需要考虑 wixor⁡wjw_i \operatorname{xor} w_j 的最大值。我们选择较小的一棵子树,穷举该子树内的每一个终止节点,使用 0/1 trie 求出该点与另一棵子树内终止节点的异或最大值(过程需要用 0/1 trie 合并维护)。

    这仍然是一个启发式合并。

    时间复杂度 O(nlog⁡2n)O(n \log^2 n)。

    #include <bits/stdc++.h>
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    const int N = 100100;
    const int SIZE = N * 2;
    
    int n;
    std::string str;
    
    int w[N];
    
    int root[SIZE];
    std::vector<int> g[SIZE];
    
    namespace trie {
        int NodeCount;
        struct node {
            int trans[2];
        } t[SIZE * 32];
    
        int create() {
            int p = ++ NodeCount;
            t[p].trans[0] = t[p].trans[1] = 0;
            return p;
        }
    
        void init() {
            NodeCount = 0;
            for (int i = 1; i <= n * 2; i ++) {
                root[i] = 0;
                g[i].clear();
            }
        }
    
        void insert(int &p, int d, int x) {
            p = create();
            if (d < 0) return;
            int v = x >> d & 1;
            insert(t[p].trans[v], d - 1, x);
        }
    
        int merge(int p, int q) {
            if (!p || !q) return p ^ q;
            t[p].trans[0] = merge(t[p].trans[0], t[q].trans[0]);
            t[p].trans[1] = merge(t[p].trans[1], t[q].trans[1]);
            return p;
        }
    
        int ask(int p, int d, int x) {
            if (d < 0) return 0;
            int v = x >> d & 1;
            if (t[p].trans[v ^ 1]) {
                return ask(t[p].trans[v ^ 1], d - 1, x) + (1 << d);
            } else {
                return ask(t[p].trans[v], d - 1, x);
            }
        }
    }
    
    int ans;
    
    namespace SAM {
        int NodeCount = 1, Last = 1;
        struct node {
            int trans[26];
            int link, maxl;
        } t[SIZE];
    
        int create() {
            int p = ++ NodeCount;
            for (int i = 0; i < 26; i ++) t[p].trans[i] = 0;
            t[p].link = t[p].maxl = 0;
            return p;
        }
    
        void init() {
            NodeCount = 0;
            Last = create();
        }
    
        void extend(int c, int i) {
            int p = Last,
                np = Last = create();
            
            t[np].maxl = t[p].maxl + 1;
            
            for (; p && t[p].trans[c] == 0; p = t[p].link) t[p].trans[c] = np;
    
            if (!p) {
                t[np].link = 1;
            } else {
                int q = t[p].trans[c];
    
                if (t[q].maxl == t[p].maxl + 1) {
                    t[np].link = q;
                } else {
                    int nq = ++ NodeCount; t[nq] = t[q]; t[nq].maxl = t[p].maxl + 1;
                    t[np].link = t[q].link = nq;
    
                    for (; p && t[p].trans[c] == q; p = t[p].link) t[p].trans[c] = nq;
                }
            }
    
            trie::insert(root[np], 16, w[i]);
            g[np].push_back(w[i]);
        }
    
        std::vector<int> son[SIZE];
        
        void build_tree() {
            for (int i = 1; i <= NodeCount; i ++) {
                son[i].clear();
            }
            for (int i = 2; i <= NodeCount; i ++) {
                son[t[i].link].push_back(i);
            }
        }
    
        void solve(int u) {
            for (int v : son[u]) {
                solve(v);
    
                if (g[u].size() < g[v].size()) {
                    std::swap(g[u], g[v]);
                    std::swap(root[u], root[v]);
                }
    
                for (int x : g[v]) {
                    chmax(ans, t[u].maxl + trie::ask(root[u], 16, x));
                    g[u].push_back(x);
                }
                root[u] = trie::merge(root[u], root[v]);
                g[v].clear();
            }
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n;
        std::cin >> str, str = " " + str;
        
        for (int i = 1; i <= n; i ++) {
            std::cin >> w[i];
        }
    
        trie::init();
        SAM::init();
    
        for (int i = n; i >= 1; i --) {
            SAM::extend(str[i] - 'a', i);
        }
    
        SAM::build_tree();
    
        ans = 0;
        SAM::solve(1);
    
        std::cout << ans << '\n';
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/