求条（20pts）+ 玄关

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e6 + 5;
struct BIT {
    ll c[N], n;
    inline void build (int x) {n = x;}
    inline void update (int x, int vl) {
        for (; x <= n; x += (x & -x))
            c[x] += vl;
    }
    inline ll sum (int x) {
        int ret = 0;
        for (; x > 0; x -= (x & -x))
            ret += c[x];
        return ret;
    }
    inline ll query (int l, int r) {
        return sum (r) - sum (l - 1);
    }
};
struct AC {
    BIT ct;
    struct node {
        int son[26], id;
    } tr[N];
    int tot, fail[N], lis[N], dfn[N], sz[N], stk[N], f[N][22], dep[N];
    vector <int> g[N];
    inline void insert (const string &s, int vl) {
        int p = 0;
        for (auto c : s) {
            int v = c - 'a';
            if (!tr[p].son[v])
                tr[p].son[v] = ++tot;
            p = tr[p].son[v];
        }
        tr[p].id = vl;
        lis[vl] = p;
    }
    inline int lca (int u, int v) {
        if (dep[u] < dep[v]) swap (u, v);
        for (int i = 21; i >= 0; i--) {
            if (dep[f[u][i]] >= dep[v]) u = f[u][i];
        }
        if (u == v) return u;
        for (int i = 21; i >= 0; i--) {
            if (f[u][i] != f[v][i]) {
                u = f[u][i];
                v = f[v][i];
            }
        }
        return f[u][0];
    }
    inline void init () {
        for (int j = 1; (1 << j) <= tot - 1; j++)
            for (int i = 1; i <= tot - 1; i++)
                f[i][j] = f[f[i][j - 1]][j - 1];
    }
    inline void dfs (int u, int fa) {
        dfn[u] = ++tot;
        dep[u] = dep[fa] + 1;
        f[u][0] = fa;
        sz[u] = 1;
        for (auto v : g[u]) {
            dfs (v, u);
            sz[u] += sz[v];
        }
    }
    inline void build_fail () {
        queue <int> q;
        for (int i = 0; i < 26; i++) {
            int v = tr[0].son[i];
            if (v) {
                q.push (v);
                fail[v] = 0;
                g[0].push_back (v);
            }
        }
        while (!q.empty ()) {
            int u = q.front ();
            q.pop ();
            for (int i = 0; i < 26; i++) {
                int v = tr[u].son[i];
                if (v) {
                    q.push (v);
                    fail[v] = tr[fail[u]].son[i];
                    g[tr[fail[u]].son[i]].push_back (v);
                }
                else tr[u].son[i] = tr[fail[u]].son[i];
            }
        }
        tot = 0;
        dfs (0, 0);
        ct.build (tot);
        init ();
    }
    inline void push (const string &s) {
        int m, p;
        m = p = 0;
        for (auto c : s) {
            int v = c - 'a';
            p = tr[p].son[v];
            stk[++m] = p;
        }
        sort (stk + 1, stk + m + 1);
        m = unique (stk + 1, stk + m + 1) - stk - 1;
        for (int i = 1; i <= m; i++) {
            ct.update (dfn[stk[i]], 1);
            if (i) ct.update (dfn[lca (stk[i], stk[i - 1])], -1);
        }
    }
    inline ll count (int x) {
        int l = dfn[lis[x]];
        int r = l + sz[lis[x]] - 1;
        return ct.query (l, r);
    }
} ac;
string s[N];
map <string, int> mp;
int n, q;
int main () {
    ios :: sync_with_stdio (0);
    cin.tie (0), cout.tie (0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        if (!mp[s[i]]) {
            mp[s[i]] = i;
            ac.insert (s[i], i);
        }
    }
    ac.build_fail ();
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            string t;
            cin >> t;
            ac.push (t);
        }
        else {
            int x;
            cin >> x;
            cout << ac.count (mp[s[x]]) << "\n";
        }
    }
    return 0;
}