Cod sursă (job #719269)

#include <bits/stdc++.h>
#include <cxxabi.h>
using namespace std;
#define ull unsigned long long int
const ull B = 18312987;

mt19937 rng(time(0));
ull pw[100000];

struct Treap {
	struct Node {
		int l = 0, r = 0, sz = 0, pri;
		char chr = '\0'; 
		ull has = 0;
	};
	vector<Node> T;
	Treap(int n) : T(n + 1) { 
		for (int i = 1; i <= n; ++i) {
			T[i].pri = rng();
			pull(i);
		}
	}
	inline void pull(int x) {
		if (!x) 
			return;
		int &l = T[x].l, &r = T[x].r;
		T[x].sz = T[l].sz + T[r].sz + 1;
		T[x].has = (T[l].has * B + T[x].chr) * pw[T[r].sz] + T[r].has;
	}
	inline void Get(int x, int l, int r, ull& ans) {
		if (x == 0 || r <= 0 || l >= T[x].sz) 
			return;
		if (l <= 0 && r >= T[x].sz) {
			ans = ans * pw[T[x].sz] + T[x].has;
			return;
		}
		Get(T[x].l, l, r, ans);
		int sz = T[T[x].l].sz;
		if (sz >= l && sz < r) 
			ans = ans * B + T[x].chr;
		Get(T[x].r, l - sz - 1, r - sz - 1, ans); 
	}
	inline pair<int, int> Split(int x, auto&& is_lhs) {
		if (!x) 
			return {0, 0};
		int l, r;
		if (is_lhs(x)) 
			tie(T[x].r, r) = Split(T[x].r, is_lhs), l = x;
		else 
			tie(l, T[x].l) = Split(T[x].l, is_lhs), r = x;
		pull(x); 
		return {l, r};
	}
	inline pair<int, int> SplitByKth(int x, int k) {
		return Split(x, [&](int y) {
			int sz = T[T[y].l].sz + 1; 
			return k >= sz ? (k -= sz, 1) : 0;
		});
	}
	inline int Join(int l, int r) {
		if (!l || !r) 
			return l + r;
		if (T[l].pri < T[r].pri)
			return T[l].r = Join(T[l].r, r), pull(l), l;
		return T[r].l = Join(l, T[r].l), pull(r), r;
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	ifstream cin("sir3.in");
	ofstream cout("sir3.out");
	string s; 
	cin >> s;
	Treap T(60000);
	pw[0] = 1;
	for (int i = 1; i < 100000; ++i)
		pw[i] = pw[i - 1] * B;
	int n = s.size();
	for (int i = 1; i <= n; ++i) {
		T.T[i].chr = s[i - 1];
		T.pull(i);
	}
	int m; 
	cin >> m;
	vector<ull> qry(m);
	vector<int> len(m);
	for (int i = 0; i < m; ++i) {
		string s; cin >> s;
		ull h = 0;
		for (auto c : s) 
			h = h * B + c;
		qry[i] = h;
		len[i] = s.size();
	}
	int rt = 0;
	for (int i = 1; i <= n; ++i)
		rt = T.Join(rt, i);
	int q; 
	cin >> q;
	int last = 0;
	while (q--) {
		int t, pos, ind, x[2]; 
		char c;
		cin >> t >> pos;
		if (t == 0) 
			cin >> c;
		else 
			cin >> ind;
		cin >> x[0] >> x[1];
		pos ^= x[last];
		if (t == 0) {
			int l, r;
			tie(l, r) = T.SplitByKth(rt, pos - 1);
			T.T[++n].chr = c;
			T.pull(n);
			rt = T.Join(T.Join(l, n), r);
		} else {
			ull ans = 0;
			T.Get(rt, pos - len[ind - 1], pos, ans);
			last = (ans == qry[ind - 1]);
			cout << last << '\n';
		}
	}
	return 0;
}