题解 P5287 【[HNOI2019]JOJO】

ywy_c_asm · 2019-05-13 21:45:07 · 题解

数组不清空，爆0两行泪

首先你发现这个串是由一堆二元组(x_i,c_i)构成的，然而这个匹配是基于一个个字符匹配的，看上去似乎和这些O(n)个二元组没啥关系。但是这题的最重要的性质就是如果一个前缀和一个后缀能够匹配，那么他们的除去开头的和结尾的剩下中间的所有二元组一定能匹配。举个例子：

这个显然可以有一个Border是aaabbcccacbbb，这中间的bbcccac的部分是完全匹配的二元组序列(2,b)(3,c)(1,a)(1,c)，但是开头和结尾的二元组可能长度有所不同，具体来说，后缀的开头长度不小于前缀，结尾长度不超过前缀，我们需要让他同时满足这两个条件才能够匹配。

很显然那个2的可持久化操作我们需要离线建棵树然后dfs（其实在线在这棵树上做做应该也是可以的……），我们就考虑当前点到根的串就行了。

既然那中间的二元组需要严格的匹配，那我们不妨把这个求一个next，而且既然我的第一个二元组可以在长度上不严格的匹配，干脆就在构建next数组的时候特判一下与第一个二元组的匹配不就行了？这样我们就只需考虑结尾的二元组了，而我们也正是要考虑结尾添加一个二元组会增加多少答案，这样好。

这里要特别注意的是，由于我们现在是在树上跑next，然而普通串上的复杂度是均摊O(n)的，放到树上复杂度就不对了……（这显然可以造一条链，底下挂个菊花来卡），因此我们需要像自动机一样令nxt[i][c][x]为在与i号点这个前缀一样的后缀后面加个二元组(x,c)，next应该到哪，这个nxt[i][c]可以套路的用主席树存，它可以直接从next[i]转移过来，然后单点修改。

（接下来为了方便描述，我们就称这个串的fail树为每个二元组的位置以next为父亲构建的树，要注意与这棵询问的树区分开）

然后我们考虑添加一个二元组(x,c)，我们肯定要考虑它的上一个位置u的fail树上到根的一条祖先链，新加的这x个字符可能就会把next继承自这条链上的某个后继字符为c的祖先，然而，这样的祖先会有很多，但是我们希望找到的next尽量长（毕竟是最长的Border），我们以这张图为例：

（其中黑色部分是这条fail链，红色的是一个长度为x的二元组(x,c)，这是我们当前在添加的新二元组，上面3个蓝色的是后继字符为c的3个祖先的二元组）

我们对[1,x]所有的新添加的c字符进行分段考虑，[1,x_3]这个部分显然就要找(x3,c)这个祖先进行匹配，对于任意的i\in[1,x_3]，next_i=deep_{(x_3,c)}+i，同理对于任意的i\in[x_3+1,x_2]，next_i=deep_{(x_2,c)}+i，对于i>x2，next_i显然就是0了。那么我们可以把这个拆成两部分，我们设mx[i][c]为i的所有fail祖先中，后继字符为c的最长的x，那么显然在[1,\min(mx[u][c],x)]这个部分里的next是有值的，它们肯定要加i，那么可以先把\sum_{i=1}^{\min(mx[u][c],x)}i这个等差数列的和加到答案里，然后就是考虑能够匹配的祖先的深度之和了。注意到我们在dfs的时候，深度显然是递增的，那么我们可以用区间强行赋值！令f[i][c][x]为i的fail祖先对一个在后面x位置的c字符的最大的贡献，这个仍然用主席树存，我们每遇到一个(x,c)，都把[1,x]这个区间强行赋为当前点的深度因为这一定是最优的，这样在主席树上区间求和就行了。

另外我们需要特判像下面这样的这种情况：

考虑最后一段(6,a)的next数组依次为1,2,3,4,4,4，而不是1,2,3,4,0,0，这是因为匹配的是第一个二元组，这个特判一下就好了。

上代码~

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
#define p 998244353
#define up(_o) data[_o] = (data[lef[_o]] + data[rgh[_o]]) % p
using namespace std;
namespace ywy {
    inline int get() {
        int n = 0;
        char c;
        while ((c = getchar()) || 23333) {
            if (c >= '0' && c <= '9')
                break;
            if (c == '-')
                goto s;
        }
        n = c - '0';
        while ((c = getchar()) || 23333) {
            if (c >= '0' && c <= '9')
                n = n * 10 + c - '0';
            else
                return (n);
        }
    s:
        while ((c = getchar()) || 23333) {
            if (c >= '0' && c <= '9')
                n = n * 10 - c + '0';
            else
                return (n);
        }
    }
    inline char cget() {
        char c;
        while ((c = getchar()) || 23333)
            if (c >= 'a' && c <= 'z')
                return (c);
    }
    typedef struct _b {
        int dest;
        int nxt;
        int x;
        int c;
    } bian;
    bian memchi[1000001], stk[100011];
    int gn = 1, heads[200001], f[200011][26], nxt[200011][26];
    inline void add(int s, int t, int x, int c) {
        memchi[gn].dest = t;
        memchi[gn].nxt = heads[s];
        memchi[gn].x = x;
        memchi[gn].c = c;
        heads[s] = gn;
        gn++;
    }
    int lef[20000001], rgh[20000001];
    int data[20000001], anss[200001], changes[20000001];
    int id[200001], gseg = 1;
    int set(int rl, int rr, int l, int r, int tree, int x, int chg) {
        int me = gseg;
        gseg++;
        if (rl == l && rr == r) {
            changes[me] = x;
            data[me] = (x * (ll)(r - l + 1)) % p;
            return (me);
        }
        int mid = (l + r) >> 1;
        if (changes[tree])
            chg = changes[tree];
        if (rl > mid) {
            if (chg) {
                lef[me] = gseg;
                gseg++;
                changes[lef[me]] = chg;
                data[lef[me]] = (chg * (mid - l + 1)) % p;
                rgh[me] = set(rl, rr, mid + 1, r, rgh[tree], x, chg);
            } else
                lef[me] = lef[tree], rgh[me] = set(rl, rr, mid + 1, r, rgh[tree], x, 0);
        } else {
            if (rr <= mid) {
                if (chg) {
                    rgh[me] = gseg;
                    gseg++;
                    changes[rgh[me]] = chg;
                    data[rgh[me]] = (chg * (ll)(r - mid)) % p;
                    lef[me] = set(rl, rr, l, mid, lef[tree], x, chg);
                } else
                    rgh[me] = rgh[tree], lef[me] = set(rl, rr, l, mid, lef[tree], x, 0);
            } else {
                lef[me] = set(rl, mid, l, mid, lef[tree], x, chg);
                rgh[me] = set(mid + 1, rr, mid + 1, r, rgh[tree], x, chg);
            }
        }
        up(me);
        return (me);
    }
    int query(int rl, int rr, int l, int r, int tree) {
        if (!tree)
            return (0);
        int mid = (l + r) >> 1;
        if (changes[tree])
            return ((changes[tree] * (ll)(rr - rl + 1)) % p);
        if (rl == l && rr == r)
            return (data[tree]);
        if (rl > mid)
            return (query(rl, rr, mid + 1, r, rgh[tree]));
        if (rr <= mid)
            return (query(rl, rr, l, mid, lef[tree]));
        return ((query(rl, mid, l, mid, lef[tree]) + query(mid + 1, rr, mid + 1, r, rgh[tree])) % p);
    }
    int sp = 1, fail[200001], mx[200001][26];
    inline ll dft(ll n) { return (((n * (n + 1)) >> 1) % p); }
    void dfs(int pt, int deep) {
        for (register int i = heads[pt]; i; i = memchi[i].nxt) {
            if (pt) {
                for (register int j = 0; j < 26; j++)
                    mx[pt][j] = mx[fail[pt]][j], f[pt][j] = f[fail[pt]][j], nxt[pt][j] = nxt[fail[pt]][j];
            } else {
                for (register int j = 0; j < 26; j++) mx[pt][j] = 0, f[pt][j] = 0, nxt[pt][j] = 0;
            }
            if (pt == 0)
                stk[1] = memchi[i];
            fail[memchi[i].dest] = query(memchi[i].x, memchi[i].x, 1, 10000, nxt[pt][memchi[i].c]);
            if (pt == 0) {
                anss[memchi[i].dest] = dft(memchi[i].x - 1);
            } else {
                if (!fail[pt]) {
                    if (memchi[i].c != stk[1].c)
                        anss[memchi[i].dest] = anss[pt];
                    else
                        anss[memchi[i].dest] =
                            (anss[pt] + dft(min(memchi[i].x, mx[pt][memchi[i].c])) +
                             (ll)(memchi[i].x - min(memchi[i].x, mx[pt][memchi[i].c])) * mx[pt][memchi[i].c]) %
                            p;
                } else {
                    anss[memchi[i].dest] = (anss[pt] + dft(min(memchi[i].x, mx[pt][memchi[i].c])) +
                                            (ll)query(1, memchi[i].x, 1, 10000, f[pt][memchi[i].c])) %
                                           p;
                    if (memchi[i].x > mx[pt][memchi[i].c] && memchi[i].c == stk[1].c) {
                        anss[memchi[i].dest] =
                            (anss[memchi[i].dest] + stk[1].x * (ll)(memchi[i].x - mx[pt][memchi[i].c])) % p;
                    }
                }
            }
            f[pt][memchi[i].c] = set(1, memchi[i].x, 1, 10000, f[fail[pt]][memchi[i].c], deep, 0);
            if (pt == 0) {
                nxt[pt][memchi[i].c] =
                    set(memchi[i].x, 10000, 1, 10000, nxt[fail[pt]][memchi[i].c], memchi[i].dest, 0);
            } else
                nxt[pt][memchi[i].c] =
                    set(memchi[i].x, memchi[i].x, 1, 10000, nxt[fail[pt]][memchi[i].c], memchi[i].dest, 0);
            mx[pt][memchi[i].c] = max(mx[fail[pt]][memchi[i].c], memchi[i].x);
            dfs(memchi[i].dest, deep + memchi[i].x);
        }
    }
    void ywymain() {
        int n = get();
        int cur = 0, gpt = 1;
        for (register int i = 1; i <= n; i++) {
            int op = get();
            if (op == 2)
                cur = id[get()];
            else {
                int x = get();
                char c = cget();
                add(cur, gpt, x, c - 'a');
                cur = gpt;
                gpt++;
            }
            id[i] = cur;
        }
        dfs(0, 0);
        for (register int i = 1; i <= n; i++) printf("%d\n", anss[id[i]]);
    }
}
int main() {
    ywy::ywymain();
    return (0);
}