分析

考虑有动态加字符串的操作，考虑 维护。然后支持一下链上加和单点查询就好了。是挺板子的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 400000;
void change(char *s,int ma) {
    int len = strlen(s);
    for(int j = 0;j < len;j++) {
        ma = (ma * 131ll + j) % len;
        swap(s[ma],s[j]);
    }
    for(int j = len;j >= 1;j--) s[j] = s[j - 1];
    s[len + 1] = '\0';
}
struct LCT {
    int fa[N],ch[N][2],s[N],add[N];
    bool nroot(int x) {return ch[fa[x]][0] == x || ch[fa[x]][1] == x;}
    void pusha(int x,int val) {add[x] += val;s[x] += val;}
    void pushdown(int x) {
        if(add[x]) {
            if(ch[x][0]) pusha(ch[x][0],add[x]);
            if(ch[x][1]) pusha(ch[x][1],add[x]);
            add[x] = 0;
        }
    }
    void push(int x) {if(nroot(x)) push(fa[x]);pushdown(x);}
    void rot(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;
    }
    void splay(int x) {
        push(x);while(nroot(x)) {
            int y = fa[x],z = fa[y];
            if(nroot(y)) rot((ch[y][1]==x)^(ch[z][1]==y)?x:y);
            rot(x);
        }
    }
    void access(int x) {for(int y = 0;x;x = fa[y=x]) splay(x),ch[x][1] = y;}
    void link(int x,int y) {fa[x] = y;access(y);splay(y);pusha(y,s[x]);}
    void cut(int x,int y) {access(x);splay(x);pusha(ch[x][0],-s[x]);fa[ch[x][0]]=0;ch[x][0]=0;}
}t;
struct SAM {
    int size,last,len[N],fa[N],nxt[N][26];
    void init() {last=size=1;}
    void ins(int c) {
        int cur = ++size;len[cur]=len[last]+1;
        int p = last;t.s[cur]=1;
        for(;p&&!nxt[p][c];p=fa[p])nxt[p][c]=cur;
        if(!p) fa[cur]=1,t.link(cur,1);
        else {
            int q=nxt[p][c];
            if(len[q]==len[p]+1)fa[cur]=q,t.link(cur,q);
            else {
                int cl=++size;fa[cl]=fa[q];len[cl]=len[p]+1;
                t.link(cl,fa[q]);
                for(int i=0;i<26;i++)nxt[cl][i]=nxt[q][i];
                for(;p&&nxt[p][c]==q;p=fa[p])nxt[p][c]=cl;    
                t.cut(q,fa[q]);t.link(cur,cl);t.link(q,cl);
                fa[cur]=fa[q]=cl;
            }
        }

        last=cur;
    }
    int query(char *s) {
        int u = 1,len = strlen(s + 1);
        for(int i = 1;i <= len;i++) {
            int c = s[i] - 'A';
            if(!nxt[u][c]) return 0;
            else u = nxt[u][c];
        }
        t.splay(u);return t.s[u];
    }
    void insert(char *s) {
        int len = strlen(s + 1);
        for(int i = 1;i <= len;i++) {
            int c = s[i] - 'A';ins(c);
        }
    }
}s;

int main() {
    s.init();int mask = 0;
    int Q;scanf("%d",&Q);
    static char S[N];
    scanf("%s",S + 1);
    s.insert(S);
    while(Q--) {
        static char op[100],ch[N];
        scanf("%s%s",op,ch);
        change(ch,mask);
        if(op[0] == 'Q') {
            int ans = s.query(ch);
            mask ^= ans;
            printf("%d\n",ans);
        }
        else s.insert(ch);
    }
}