「模拟测试」背单词-AC 自动机+二进制分组

/**
 * Copyright (c) 2017-2018, xehoth
 * All rights reserved.
 * words 16-01-2018
 * AC 自动机 + 二进制分组
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace {

inline char read() {
    static const int IN_LEN = 1 << 18 | 1;
    static char buf[IN_LEN], *s, *t;
    return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)),
           s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        iosig |= c == '-';
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig && (x = -x);
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1 << 18 | 1;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    (oh == obuf + OUT_LEN) && (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf);
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[21], cnt;
    if (x != 0) {
        (x < 0) && (print('-'), x = -x);
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    } else {
        print('0');
    }
}

struct InputOutputStream {
    ~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }

    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }
} io;

typedef unsigned long long ulong;

const int MAXN = 100000 + 9;
const int SIGMA = 26;

char *cur;

const int MAXM = 2000000 + 9;

char buc[MAXN], *s[MAXN];
int idx, val[MAXN];
int n, type;

struct AhoCorasickAutomation {
    struct Node {
        static const int NODE_SIZE;
        Node *fail, *c[SIGMA];
        ulong val;

        inline void *operator new(size_t) { return cur += NODE_SIZE; }
    };
    Node *null, *root;

    inline void init(Node *p) {
        p->fail = null;
        for (register int i = 0; i < SIGMA; i++) p->c[i] = null;
    }

    inline void init() {
        root = new Node();
        null = new Node();
        null->fail = null;
        for (register int i = 0; i < SIGMA; i++) null->c[i] = root;
        init(root);
    }

    inline void insert(int w) {
        register Node *p = root;
        for (register char *c = s[w]; *c; c++) {
            if (p->c[*c - 'a'] == null) init(p->c[*c - 'a'] = new Node());
            p = p->c[*c - 'a'];
        }
        p->val += val[w];
    }

    inline void build() {
        std::queue<Node *> q;
        q.push(root);
        for (register Node *p, *u; !q.empty();) {
            p = q.front();
            q.pop();
            for (register int i = 0; i < SIGMA; i++) {
                if (p->c[i] != null) {
                    for (u = p->fail; u->c[i] == null;) u = u->fail;
                    p->c[i]->fail = u->c[i];
                    q.push(p->c[i]);
                    p->c[i]->val += u->c[i]->val;
                } else {
                    p->c[i] = p->fail->c[i];
                }
            }
        }
    }

    inline long long query() {
        register long long ret = 0;
        register Node *p = root;
        for (register char *c = buc; *c; c++) {
            p = p->c[*c - 'a'];
            ret += p->val;
        }
        return ret;
    }
} d[MAXN];

const int AhoCorasickAutomation::Node::NODE_SIZE =
    sizeof(AhoCorasickAutomation::Node);

char pool[MAXM * AhoCorasickAutomation::Node::NODE_SIZE];

inline void build() {
    register int begin = idx - (idx & -idx) + 1;
    if (begin < idx)
        cur = (char *)d[begin].root - AhoCorasickAutomation::Node::NODE_SIZE;
    d[idx].init();
    for (register int i = begin; i <= idx; i++) d[idx].insert(i);
    d[idx].build();
}

inline long long query() {
    register long long ret = 0;
    for (register int k = idx; k; k ^= k & -k) ret += d[k].query();
    return ret;
}

inline void solve() {
    cur = pool;
    io >> n >> type;
    register long long ans = 0;
    for (register int cmd, len; n--;) {
        io >> cmd;
        len = read(buc);
        if (type) {
            for (register int i = 0; i < len; i++)
                buc[i] = ((buc[i] - 'a') ^ ans) % 26 + 'a';
        }
        switch (cmd) {
            case 0: {
                s[++idx] = new char[len + 1]();
                memcpy(s[idx], buc, len);
                io >> val[idx];
                build();
                break;
            }
            case 1: {
                ans = query();
                io << ans << '\n';
                break;
            }
        }
    }
}
}  // namespace

int main() {
    // freopen("sample/1.in", "r", stdin);
    solve();
    return 0;
}