Cod sursă (job #618374)

#include <bits/stdc++.h>
 
using namespace std;
 
const int kLenmax = 60005;
 
const int kMod1 = 1e9+9;
const int kBase1 = 27;
int pw1[kLenmax];
 
const int kMod2 = 1e9+7;
const int kBase2 = 29;
int pw2[kLenmax];
 
struct Node {
    int left = 0, right = 0;
    int val, pri;
    int h1 = 0, h2 = 0;
    int cnt = 0;
 
    Node(char val_, int pri_) : val(val_), pri(pri_) {}
};
 
struct Treap {
    int root;
    vector<Node> T;
    
    Treap() : root(0), T(1, Node(-1, -1)) {}
 
    int index_of(int node) {
        return T[T[node].left].cnt;
    }
 
    int hcomb(int b, int m, int pw[kLenmax], int hleft, int hright, int v, int cntright) {
        hleft = (1LL * hleft * b + v) % m;
        hleft = (1LL * hleft * pw[cntright] + hright) % m;
        return hleft;
    }
 
    int pull(int node) {
        if (!node) return node;
 
        T[node].h1 = hcomb(kBase1, kMod1, pw1, T[T[node].left].h1, T[T[node].right].h1, T[node].val, T[T[node].right].cnt);
        T[node].h2 = hcomb(kBase2, kMod2, pw2, T[T[node].left].h2, T[T[node].right].h2, T[node].val, T[T[node].right].cnt);
        T[node].cnt = T[T[node].left].cnt + T[T[node].right].cnt + 1;
 
        return node;
    }
 
    int Join(int l, int r) {
        if (!l) return r;
        if (!r) return l;
 
        if (T[l].pri > T[r].pri) {
            T[l].right = Join(T[l].right, r);
            return pull(l);
        } else {
            T[r].left = Join(l, T[r].left);
            return pull(r);
        }
    }
 
    pair<int, int> Split(int node, int key) {
        if (!node) return {0, 0};
 
        if (index_of(node) < key) {
            int l, r;
            tie(l, r) = Split(T[node].right, key - index_of(node) - 1);
            T[node].right = l;
            return {pull(node), r};
        } else {
            int l, r;
            tie(l, r) = Split(T[node].left, key);
            T[node].left = r;
            return {l, pull(node)};
        }
    }
 
    int One(char c) {
        int node = T.size();
        T.emplace_back(Node(c, rand()));
        return pull(node);
    }
 
    void Insert(int pos, char c) {
        int l, r;
        tie(l, r) = Split(root, pos);
        root = Join(l, Join(One(c), r));
    }
 
    pair<int, int> Between(int b, int e) {
        int l, m, r;
        tie(m, r) = Split(root, e);
        tie(l, m) = Split(m, b);
        auto ans = make_pair(T[m].h1, T[m].h2);
        root = Join(l, Join(m, r));
        return ans;
    }
};
 
vector<pair<int, pair<int, int>>> dict;
int n, k, q;
char s[kLenmax];
 
int main() {
    Treap t;
 
    srand(time(nullptr));
    freopen("sir8.in", "r", stdin);
    freopen("sir8.out", "w", stdout);
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    pw1[0] = 1;
    pw2[0] = 1;
    for (int i = 1; i < kLenmax; i++) {
        pw1[i] = (1LL * pw1[i - 1] * kBase1) % kMod1;
        pw2[i] = (1LL * pw2[i - 1] * kBase2) % kMod2;
    }
 
    cin >> (s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) t.Insert(i - 1, s[i]);
 
    cin >> k;
    for (int i = 1; i <= k; i++) {
        string s;
        cin >> s;
        int h1, h2;
        h1 = h2 = 0;
 
        for (char c : s) {
            h1 = (1LL * h1 * kBase1 + c) % kMod1;
            h2 = (1LL * h2 * kBase2 + c) % kMod2;
        }
 
        dict.push_back({s.size(), {h1, h2}});
    }
 
    cin >> q;
    int last_query = 0;
    for (int i = 1, op, pos, a, b; i <= q; i++) {
        cin >> op >> pos;
        if (op == 1) {
            int ind;
            cin >> ind >> a >> b;
 
            pos ^= last_query ? b : a;
            if (pos < dict[ind - 1].first) last_query = 0;
            else {
                auto x = t.Between(pos - dict[ind - 1].first, pos);
                last_query = dict[ind - 1].second == x;
            }
 
            cout << last_query << '\n';
        } else {
            char c;
            cin >> c >> a >> b;
            pos ^= last_query ? b : a;
            t.Insert(pos - 1, c);
        }
    }
 
    return 0;
}