「CSP-S 2019」括号树plus

    「CSP-S 2019」括号树plus

    CLYZ 学长学姐们留下来的题,感谢+膜拜。

    给出一棵有 nn 个节点的数,根节点为 11。每个节点上恰有一个括号,要么为左括号 ( 要么为右括号 )。

    记 sis_i 表示从根到 ii 的路径上,依次将各个节点的括号拼接而成的字符串。设 kik_i 表示 sis_i 中本质不同的合法括号子串的数量。求

    (1×k1)xor(2×k2)xor⋯xor(n×kn).(1 \times k_1) \mathbin{\mathrm{xor}} (2 \times k_2) \mathbin{\mathrm{xor}} \dots \mathbin{\mathrm{xor}} (n \times k_n).

    数据范围:1≤n≤5×1051 \leq n \leq 5 \times 10^5。

    时空限制:55s / 512512MiB。

    Solution

    采用增量法。对树进行 DFS,每次计算以 uu 为最低点时的答案。

    由于要求本质不同,对于一个串 s[u:tu]s[u : t_u],如果其在 s[Fau:1]s[\mathrm{Fa}_u : 1] 中作为子串出现,则这样的串是不能计入答案的。

    求一个深度最小的 tut_u,相当于是在 Fau\mathrm{Fa}_u 到 11 的路径上选一个点 vv,使得 LCP(s[u:1],s[v:1])\mathrm{LCP}(s[u : 1], s[v : 1]) 最大。

    在树上做一遍 SA,这相当于是在 Fau\mathrm{Fa}_u 到 11 的路径上,找 rku\mathrm{rk}_u 的前驱后继。用 std::set 维护即可。

    考虑求在 Fatu\mathrm{Fa}_{t_u} 到 11 的路径上,有多少个点 vv 使得 s[u:v]s[u : v] 是一个合法括号串。

    将左右括号转换为 ±1\pm 1 做一个前缀和。用倍增找出可行范围后,在 std::vector 上二分维护即可。

    时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <set>
    #include <vector>
    
    typedef long long s64;
    
    using std::set;
    typedef set<int>::iterator iter;
    
    using std::vector;
    
    template <class T>
    inline void read(T &x) {
        static char s;
        while (s = getchar(), s < '0' || s > '9');
        x = s - '0';
        while (s = getchar(), s >= '0' && s <= '9') x = x * 10 + s - '0';
    }
    
    void tense(int &x, const int &y) {
        if (x < y) x = y;
    }
    
    void relax(int &x, const int &y) {
        if (x > y) x = y;
    }
    
    const int N = 500100;
    
    int n;
    char s[N];
    
    int anc[19][N];
    
    int tot, head[N], ver[N], Next[N];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int pre[N];
    int dep[N];
    int g[19][N];
    
    void dfs1(int u) {
        pre[u] = pre[anc[0][u]] + (s[u] == '(' ? -1 : 1);
        dep[u] = dep[anc[0][u]] + 1;
    
        for (int i = 1; i <= 18; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];
    
        g[0][u] = pre[anc[0][u]];
        for (int i = 1; i <= 18; i ++) tense(g[i][u] = g[i - 1][u], g[i - 1][anc[i - 1][u]]);
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            dfs1(v); 
        }
    }
    
    namespace SA {
        int m = 2;
        int sa[N], rk[N], height[N];
        int cnt[N], id[N], px[N];
        int anc_rk[19][N];
    
        int get_LCP(int x, int y) {
            int cur = 0;
            for (int i = 18; i >= 0; i --) {
                if (std::min(dep[x], dep[y]) < (1 << i)) continue;
                if (anc_rk[i][x] ^ anc_rk[i][y]) continue;
                x = anc[i][x], y = anc[i][y], cur ^= (1 << i);
            }
            return cur;
        }
    
        bool same(int x, int y, int k) {
            int p = anc[k][x] ? anc_rk[k][anc[k][x]] : -1;
            int q = anc[k][y] ? anc_rk[k][anc[k][y]] : -1;
            return anc_rk[k][x] == anc_rk[k][y] && p == q;
        }
    
        void build() {
            for (int i = 1; i <= n; i ++) rk[i] = (s[i] == '(' ? 1 : 2);
            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 = 0, p = 0; (1 << k) < n; k ++, m = p) {
                for (int i = 0; i <= m; i ++) cnt[i] = 0;
                for (int i = 1; i <= n; i ++) cnt[px[i] = rk[anc[k][i]]] ++;
                for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
                for (int i = n; i >= 1; i --) id[cnt[px[i]] --] = i;
    
                for (int i = 0; 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 ++) anc_rk[k][i] = rk[i];
    
                p = 0;
                for (int i = 1; i <= n; i ++) rk[sa[i]] = same(sa[i - 1], sa[i], k) ? p : ++ p;
            }
    
            for (int i = 1; i <= n; i ++) rk[sa[i]] = i;
            for (int i = 2; i <= n; i ++) height[i] = get_LCP(sa[i - 1], sa[i]);
        }
    }
    
    namespace ST {
        int logx[N];
        int f[19][N];
    
        void build() {
            logx[0] = -1;
            for (int i = 1; i <= n; i ++) logx[i] = logx[i >> 1] + 1;
    
            for (int i = 1; i <= n; i ++) f[0][i] = SA::height[i];
            for (int j = 1; j <= 18; j ++)
                for (int i = 1; i <= n - (1 << j) + 1; i ++)
                    relax(f[j][i] = f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
        }
    
        int query(int l, int r) {
            int k = logx[r - l + 1];
            return std::min(f[k][l], f[k][r - (1 << k) + 1]);
        }
    }
    
    set<int> G;
    
    int find_h(int x) {
        iter w = G.lower_bound(x);
    
        int cur = 0;
    
        if (w != G.end())
            tense(cur, ST::query(x + 1, *w));
    
        if (w != G.begin())
            tense(cur, ST::query(*(-- w) + 1, x));
    
        return cur;
    }
    
    int find_m(int u) {
        int x = u;
        for (int i = 18; i >= 0; i --)
            if (dep[x] >= (1 << i) && pre[u] >= g[i][x]) x = anc[i][x];
        return x;
    }
    
    vector<int> pos[N * 2];
    
    s64 ans[N]; 
    
    void dfs2(int u) {
        int l = dep[find_m(u)] + 1, r = dep[u] - find_h(SA::rk[u]);
    
        pos[n + pre[anc[0][u]]].push_back(dep[u]);
        G.insert(SA::rk[u]);
    
        ans[u] = ans[anc[0][u]];
        if (s[u] == ')') {
            if (l <= r) {
                vector<int> &V = pos[n + pre[u]];
                ans[u] += upper_bound(V.begin(), V.end(), r) - lower_bound(V.begin(), V.end(), l);
            }
        }
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            dfs2(v);
        }
    
        pos[n + pre[anc[0][u]]].pop_back();
        G.erase(SA::rk[u]);
    }
    
    int main() {
        read(n);
    
        scanf("%s", s + 1);
    
        for (int i = 2; i <= n; i ++)
            read(anc[0][i]), add_edge(anc[0][i], i);
    
        dfs1(1);
    
        SA::build();
        ST::build();
    
        dfs2(1);
    
        s64 res = 0;
        for (int i = 1; i <= n; i ++) res ^= (ans[i] * i);
    
        printf("%lld\n", res);
    
        return 0;
    }