bzoj2555,lct+sam

bzoj2555.cpp

#include <cstdio>
#include <cstring>
#include <string>
using std::string;
const int N = 600000 * 2 + 9;
int mask;
char s[3000000 + 9];
string chars;
void gets(int mask)
{
    scanf("%s\n",s);
    chars = s;
    for (int j = 0; j < chars.length(); j++) {
        mask = (mask * 131 + j) % chars.length();
        char t = chars[j];
        chars[j] = chars[mask];
        chars[mask] = t;
    }
}
struct lct
{
    int l[N],r[N],p[N],w[N],add[N];
    void Add(int x,int y)
    {
        if (!x) return;
        add[x] += y;
        w[x] += y;
    }
    void rls(int x)
    {
        if (add[x]) {
            Add(l[x],add[x]); Add(r[x],add[x]);
            add[x] = 0;
        }
    }
    void rig(int x)
    {
        int y = l[x];
        p[y] = p[x];
        if (l[p[y]] == x) l[p[y]] = y;
        if (r[p[y]] == x) r[p[y]] = y;
        p[r[y]] = x;
        l[x] = r[y];
        p[x] = y;
        r[y] = x;
    }
    void lef(int x)
    {
        int y = r[x];
        p[y] = p[x];
        if (l[p[y]] == x) l[p[y]] = y;
        if (r[p[y]] == x) r[p[y]] = y;
        p[l[y]] = x;
        r[x] = l[y];
        p[x] = y;
        l[y] = x;
    }
    bool isrt(int x){return !p[x] || l[p[x]] != x && r[p[x]] != x;}
    void splay(int x)
    {
        rls(x);
        while (!isrt(x)) {
            int y = p[x],z = p[y];
            if (!isrt(y)) rls(z);
            rls(y); rls(x);
            if (!isrt(y) && l[z] == y && l[y] == x) rig(z),rig(y);
            else if (!isrt(y) && r[z] == y && r[y] == x) lef(z),lef(y);
            else if (l[y] == x) rig(y);
            else lef(y);
        }
    }
    void access(int rt)
    {
        for (int y = rt,x = 0; y; y = p[y]) {
            splay(y);
            r[y] = x;
            x = y;
        }
        splay(rt);
    }
    void cut(int x)
    {
        //for (int i = p[x]; i; i = p[i]) w[i] -= w[x];
        //p[x] = 0;
        access(x);
        Add(l[x],-w[x]);
        p[l[x]] = 0; l[x] = 0;
    }
    void link(int x,int fa)
    {
        //p[x] = fa;
        //for (int i = p[x]; i; i = p[i]) w[i] += w[x];
        p[x] = fa;
        access(fa);
        Add(fa,w[x]);
    }
}t;
struct SAM
{
    int l[N],fa[N],ch[N][26],cnt,last,len;
    SAM():cnt(1),last(1){}
    void add(int c)
    {
        int np = ++cnt,p = last;
        l[np] = ++len;
        t.w[np] = 1;
        last = np;
        for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
        if (!p) fa[np] = 1,t.link(np,1);
        else {
            int q = ch[p][c];
            if (l[q] == l[p] + 1) fa[np] = q,t.link(np,q);
            else {
                int nq = ++cnt;
                memcpy(ch[nq],ch[q],sizeof ch[q]);
                l[nq] = l[p] + 1;
                t.link(nq,fa[q]);
                t.cut(q);
                t.link(q,nq);
                t.link(np,nq);
                fa[nq] = fa[q];
                fa[q] = fa[np] = nq;
                for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
            }
        }
    }
    void build()
    {
        scanf("%s",s);
        chars = s;
        for (int i = 0; i < chars.size(); ++i)
            add(chars[i] - 'A');
    }
    void add()
    {
        gets(mask);
        for (int i = 0; i < chars.size(); ++i)
            add(chars[i] - 'A');
        // for (int i = 1; i <= cnt; ++i) t.p[i] = fa[i];
    }
    int query()
    {
        gets(mask);
        int p = 1;
        for (int i = 0; i < chars.size(); ++i)
            if (!(p = ch[p][chars[i] - 'A'])) return 0;
        t.splay(p);
        return t.w[p];
    }
}sam;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("2555.in","r",stdin);
    freopen("2555.out","w",stdout);
    #endif
    int q = 0;
    scanf("%d\n",&q);
    sam.build();
    while (q--) {
        scanf("%s\n",s);
        if (s[0] == 'A') sam.add();
        else {
            int ans = sam.query();
            printf("%d\n",ans);
            mask ^= ans;
        }
    }
}