F. NIO with String Game

Solution

考虑离线，对所有t串（包括后面添加的字符）建出一棵trie树，按从a到z的顺序遍历子节点进行dfs，就可以把dfs序对应成字典序，这样就相当于每次需要在trie上找到s对应的位置，求dfs序比它小的位置上有多少个t串。
对于操作一、四：考虑用树状数组维护dfs序上的贡献前缀和，那么添加一个字符时就将当前$t_{i}t\_i$串的位置贡献去掉，走到其下一个位置，再添加上贡献，查询时只要找到需要查询的dfs序最大值即可。
对于操作二、三：考虑维护一个nows表示目前s匹配时最终走到哪个点，res表示匹配的部分后面还有多少个字符，sto表示当res不为0时第一个字符是什么。对于删除操作，如果res删完了，则需要向上跳，这里倍增一下即可；对于添加操作，可以先预处理一直跳$chch$会跳到什么地方，如果需要跳的步数较多，则跳到对应位置，记录res和sto，如果需要跳的步数较少，则从一直跳到最后的地方向上倍增，找到对应位置。
需要特别注意的是，查询时如果res为0，则查询部分不能包含nows，如果nows有小于sto的子节点，则查询的部分应该是其最大的小于sto的子树的最大dfs序。
另外，记得res要开long long，删除操作的p也可能是long long。 时间复杂度$O((n+q)(26+\log n))O((n+q)(26+\backslash log\; n))$。

char s[N], t[N];
struct Operation {
    int opt;
    ll x;
    char ch[2];
}a[N];
struct Trie {
    int c[N][26], tot = 1, loc[N], dfn[N], cnt, tree[N], fa[20][N], nt[N][26], dep[N], cov[N];
    int nows, sto;
    ll res;
    void update(int x, int data) {
        while (x <= cnt) {
            tree[x] += data;
            x += lowbit(x);
        }
    }
    int query(int x) {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
    int insert(char s[], int n, int id) {
        int now = 1;
        for (int i = 0; i < n; ++i) {
            int to = s[i] - 'a';
            if (!c[now][to])c[now][to] = ++tot;
            now = c[now][to];
        }
        return loc[id] = now;
    }
    void add(int id, int to) {
        if (!c[loc[id]][to])c[loc[id]][to] = ++tot;
        loc[id] = c[loc[id]][to];
    }
    void dfs(int x) {
        dfn[x] = ++cnt;
        for (int i = 1; i < 20; ++i)
            fa[i][x] = fa[i - 1][fa[i - 1][x]];
        for (int i = 0; i < 26; ++i) {
            if (c[x][i]) {
                fa[0][c[x][i]] = x;
                dep[c[x][i]] = dep[x] + 1;
                dfs(c[x][i]);
                nt[x][i] = nt[c[x][i]][i];
            }
            else nt[x][i] = x;
        }
        cov[x] = cnt;
    }
    void init(int n, char s[], int m) {
        dfs(1);
        for (int i = 1; i <= n; ++i)
            update(dfn[loc[i]], 1);
        nows = 1;
        res = 0;
        sto = -1;
        for (int i = 0; i < m; ++i) {
            int to = s[i] - 'a';
            if (!c[nows][to]) {
                res = m - i;
                sto = to;
                break;
            }
            else nows = c[nows][to];
        }
    }
    void change(int id, int to) {
        update(dfn[loc[id]], -1);
        loc[id] = c[loc[id]][to];
        update(dfn[loc[id]], 1);
    }
    void del(ll p) {
        if (res >= p)res -= p;
        else {
            p -= res, res = 0;
            for (int i = 0; i < 20; ++i)
                if ((p >> i) & 1)
                    nows = fa[i][nows];
        }
        if (res == 0)sto = -1;
    }
    void getnt(int k, int to) {
        if (res) {
            res += k;
            return;
        }
        int y = nt[nows][to];
        if (dep[y] - dep[nows] <= k) {
            res = k - (dep[y] - dep[nows]);
            if (res)sto = to;
            else sto = -1;
            nows = y;
        }
        else {
            res = 0;
            sto = -1;
            int del = dep[y] - dep[nows] - k;
            nows = y;
            for (int i = 0; i < 20; ++i)
                if ((del >> i) & 1)
                    nows = fa[i][nows];
        }
    }
    int getans() {
        if (sto == -1)return query(dfn[nows] - 1);
        int x = -1;
        for (int i = 0; i < sto; ++i)
            if (c[nows][i])x = max(x, cov[c[nows][i]]);
        if (x == -1)return query(dfn[nows]);
        return query(x);
    }
}T;
int p[N];

int main() {
    int n = fast_IO::read(), q = fast_IO::read();
    scanf("%s", s);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", t);
        p[i] = T.insert(t, strlen(t), i);
    }
    for (int i = 1; i <= q; ++i) {
        a[i].opt = fast_IO::read();
        if (a[i].opt == 1) {
            a[i].x = fast_IO::read();
            scanf("%s", a[i].ch);
            T.add(a[i].x, *a[i].ch - 'a');
        }
        else if (a[i].opt == 2) {
            a[i].x = fast_IO::read();
        }
        else if (a[i].opt == 3) {
            a[i].x = fast_IO::read();
            scanf("%s", a[i].ch);
        }
    }
    for (int i = 1; i <= n; ++i)T.loc[i] = p[i];
    T.init(n, s, strlen(s));
    for (int i = 1; i <= q; ++i) {
        if (a[i].opt == 1) {
            T.change(a[i].x, *a[i].ch - 'a');
        }
        else if (a[i].opt == 2) {
            T.del(a[i].x);
        }
        else if (a[i].opt == 3) {
            T.getnt(a[i].x, *a[i].ch - 'a');
        }
        else printf("%d\n", T.getans());
    }
    return 0;
}