小 丑 竟 是 我 自 己

首先本题的做法:建立SAM,用LCT维护fail树,查询fail树上和就好了

我: 这还不简单?

于是开始码吗码

锅锅锅

1. 维护虚子树要和自己的值分开
2. rotate不能写错了,一定要画图,结果我的fa还是写错一次
3. splay中一定要写对了,是两个在同一方向我们才旋转y
4. access的时候改信息
5. sam的ins函数中一定别忘了在改任何一个的fa时修改LCT
6. LCT询问原树子树和

答案是LCT上实树的右子树和+虚树和+自己值!!

7. 充分利用SAM调试必需的拓扑排序函数和outtree函数
8. 字符集是"A,B"不是"a,b"

我...好sb啊QAQ

//子树求和
//这个并不难维护,直接LCT做就好了
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e6;

int Q, lsa, T;
string s;
char t[MAXN];

namespace LCT {
#define L ch[x][0]
#define R ch[x][1]
	int ch[MAXN][2], sumx[MAXN], sum[MAXN], fa[MAXN], a[MAXN]; //虚树和+自己,总树和
	int tag[MAXN], st[MAXN];
	inline int nroot(int x) {
		return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
	}
	//LCT维护子树和
	//我们应该考虑一个点的答案实际上是左子树加上虚子树加上他自己...
	inline void pushup(int x) {
		sum[x] = sum[L] + sum[R] + sumx[x] + a[x];
	}
	inline void outtree() {
		for(int x = 1; x <= T; ++x) {
			printf("node : %d %d L %d R %d |sum! %d x %d my %d\n", x, fa[x], L, R, sum[x], sumx[x], a[x]);
		}
		puts("\n");
	}
	//不能换根!
	inline void rotate(int x) {
		int y = fa[x], z = fa[y], k = ch[y][1] == x, w = ch[x][!k];
		if(nroot(y))ch[z][ch[z][1] == y] = x;
		ch[x][!k] = y;
		ch[y][k] = w;
		if(w)fa[w] = y;
		fa[x] = z;
		fa[y] = x;
		pushup(y);
	}
	inline void pushR(int x) {
		L ^= R ^= L ^= R;
		tag[x] ^= 1;
	}
	inline void pushdown(int x) {
		if(tag[x]) {
			if(L)pushR(L);
			if(R)pushR(R);
			tag[x] = 0;
		}
	}
	inline void splay(int x) {
		int z = 0, y = x;
		st[++z] = y;
		while(nroot(y))st[++z] = y = fa[y];//从右到左
		while(z)pushdown(st[z--]);
		while(nroot(x)) {
			y = fa[x], z = fa[y];
			if(nroot(y))rotate(((ch[y][1] == x) ^ (ch[z][1] == y)) ? x : y);
			rotate(x);
		}
		pushup(x);
		return;
	}
	inline void access(int x) {
		for(int y = 0; x; x = fa[y = x]) {
			splay(x);
			sumx[x] -= sum[y];
			sumx[x] += sum[R];
			R = y;
			pushup(x);
		}
	}
	inline void link(int x, int y) {
		access(x);
		splay(x);
		access(y);
		splay(y);
		fa[y] = x;
		pushup(y);
		sumx[x] += sum[y];
		pushup(x);
	}
	inline void cut(int x, int y) {
		access(x);
		splay(x);
		access(y);
		splay(y);
		ch[y][0] = 0;
		fa[x] = 0;
		pushup(y);
	}
	//找到splay里面的根
	inline int getrt(int x) {
		splay(x);
		while(L)x = L;
		splay(x);
		return x;
	}
}

int ch[MAXN][4], fa[MAXN], len[MAXN], lst;

inline void ins(int c) {
	int p = lst;
	int np = lst = ++T;
	int nq, q;
	len[np] = len[p] + 1;
	for(; p && !ch[p][c]; p = fa[p])ch[p][c] = np;
	LCT::a[np]++;
	if(!p) {
		fa[np] = 1;
		LCT::link(1, np);//LCT!
	} else {
		q = ch[p][c];
		if(len[q] == len[p] + 1) {
			fa[np] = q;
			LCT::link(q, np);
			return;
		}
		nq = ++T;
		len[nq] = len[p] + 1;
		fa[nq] = fa[q];
		LCT::cut(fa[q], q);
		LCT::link(fa[q], nq);
		LCT::link(nq, q);
		LCT::link(nq, np);
		fa[q] = fa[np] = nq;
		memcpy(ch[nq], ch[q], sizeof(ch[q]));
		for(; ch[p][c] == q; p = fa[p])ch[p][c] = nq;
	}
	return ;
}

int a[MAXN], c[MAXN];
inline void ts() {
	for(int i = 1; i <= T; ++i)c[len[i]]++;
	for(int i = 1; i <= s.size(); ++i)c[i] += c[i - 1];
	for(int i = 1; i <= T; ++i)a[c[len[i]]--] = i;
	for(int i = T; i; --i) {
		int u = a[i];
		LCT::access(1);
		LCT::splay(1);
		printf("%d %d %d %d\n", u, fa[u], len[u], LCT::sum[u]);
	}
	return;
}

string decodeWithMask(string &s, int mask) {
	for (int j = 0; j < (int)s.size(); j++) {
		mask = (mask * 131 + j) % s.size();
		char t = s[j];
		s[j] = s[mask];
		s[mask] = t;
	}
	return s;
}

inline void solve() {
	int u = 1;
	for(int i = 0; i < (int)s.size(); ++i) {
		int t = s[i] - 'A';
		if(!ch[u][t]) {
			lsa = 0;
			return ;
		}
		u = ch[u][t];
	}
	LCT::getrt(u);
	lsa = LCT::sum[LCT::ch[u][1]] + LCT::sumx[u] + LCT::a[u];
	return ;
}

int main() {
	scanf("%d", &Q);
	cin >> s;
	lst = T = 1;
	int qwq = 0;
	for(int i = 0; i < (int)s.size(); ++i)ins(s[i] - 'A');
	for(int i = 1; i <= Q; ++i) {
		scanf("%s", t);
		if(t[0] == 'Q') {
			cin >> s;
			decodeWithMask(s, qwq);
			solve();//让他结束生命
			printf("%d\n", lsa);
			qwq ^= lsa;
		} else {
			cin >> s;
			decodeWithMask(s, qwq);
			for(int j = 0; j < (int)s.size(); ++j)ins(s[j] - 'A');
		}
	}
	return 0;
}