某岛

… : "…アッカリ~ン . .. . " .. .
March 19, 2020

BZOJ 2555. SubString

Vjudge 传送门 | BZOJ 传送门 | Luogu 传送门

SPOJ NSUBSTR2,双倍经验。
https://oi.men.ci/bzoj-2555/
https://jkloverdcoi.github.io/2019/05/04/bzoj-2555-substring/
http://www.yznheya.top/blog/?p=674
https://www.cnblogs.com/oier/p/10432031.html

动态树维护后缀自动机。样例数据你是认真的吗。。。

const int N = int(6e6) + 9, Z = 2;

int trans[N][Z], len[N], par[N], tail, tot; char s[N/2];

#define l c[0]
#define r c[1]
#define lx x->l
#define rx x->r
#define px x->p
#define ly y->l
#define ry y->r
#define py y->p

struct node{

    static node* NIL;
#define NIL node::NIL

    node *c[2], *p; //node* d[]

    int w0, delay; bool rev;

    inline void reset(int _w){
        p = c[0] = c[1] = NIL;
        w0 = _w, delay = rev = 0;
    }

    inline node(){
        //reset();
    }

    inline int sgn(){return p->l == this ? 0 : p->r == this ? 1 : -1;}
    inline void link(int d, node* x){c[d] = x; px = this;}

    inline void update(){
        //w1 = max(l->w1, w0, r->w1);
    }

    inline void inc(int d){
        if (this == NIL) return;
        w0 += d, delay += d;
    }

    inline void release(){
        //if (this == NIL) return;
        if (rev){
            swap(l, r);
            l->rev ^= 1, r->rev ^= 1;
            rev = 0;
        }
        if (delay){
            l->inc(delay), r->inc(delay);
            delay = 0;
        }
    }

    inline void _rot(int d){
        node *y = p, *z = py;
        if (y->sgn() != -1) z->link(y->sgn(), this); else p = z;
        y->link(d, c[d^1]), link(d^1, y);
        y->update();
    }

    inline void rot(){_rot(sgn());}
    inline void zig(){_rot(0);}
    inline void zag(){_rot(1);}

    inline void fix(){
        if(~sgn()) p->fix();
        release();
    }

    inline node* splay(){
        fix(); while (sgn() != -1){
            node *y = p, *z = y->p; if (y->sgn() == -1){ rot(); break;}
            if (z->l == y){
                if (y->l == this) y->zig(), zig();
                else zag(), zig();
            }else{
                if (y->r == this) y->zag(), zag();
                else zig(), zag();
            }
        }
        update();
        return this;
    }

    inline node* access(){
        node *x = this, *y = NIL; do{
            x->splay();
            rx = y, x->update();
            y = x, x = px;
        } while (x != NIL);
        return y;
    }

    inline node* accesss(){
        access();
        return splay();
    }

    node* rt(){
        node* x; for (x = access(); x->release(), lx != NIL; x = lx);
        return x;
    }

    node* evert(){
        access()->rev ^=1;
        return this;
    }

#define evertt evert()->splay
    // Public ...

    void Link(node* x){
        //if (x == NIL) return;
        access(); p = x;
        p->access()->inc(w0);
    }

    void Cut(){
        accesss(); //if (l == NIL) return;
        l->inc(-w0), l->p = NIL, l = NIL;
    }

    int Query(){
        return accesss()->w0;
    }

} TPool[N], *T[N], *NIL;

#define v trans[u]
#define p par[u]
#define pp par[uu]

inline int new_node(){
    RST(trans[tot]); T[tot]->reset(1); tail = tot;
    return tot++;
}

inline int new_node(int u){
    CPY(trans[tot], trans[u]); par[tot] = par[u];
    T[tot]->reset(0); T[tot]->Link(T[par[u]]);
    return tot++;
}

void Ext(int c){
    int u = tail, uu = new_node();len[uu] = len[u] + 1;
    while (u && !v) v = uu, u = p; // 向上遍历没有 c-转移 的祖先 ..
    if (!u && !v) v = uu, pp = 0;
    else{
        if (len[v] == len[u] + 1) pp = v, T[uu]->Link(T[v]);
        else{
            int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
            T[_v]->Cut(), T[_v]->Link(T[vv]), T[uu]->Link(T[vv]);
            par[_v] = pp = vv;
            while (v == _v) v = vv, u = p;
        }
    }
}

#define c (*cc - 'A')
void Init(){
    tot = 0, tail = new_node();
    RS(s); REP_S(cc, s) Ext(c);
}

int mask;

void get() {
    int t = mask;
    RS(s); int n = strlen(s);
    REP(i, n) {
        t = (t * 131 + i) % n;
        swap(s[i], s[t]);
    }
}

void Query() {
    int u = 0; get(); REP_S(cc, s) if (!(u = v)) break;
    int ans = u ? T[u]->Query() : 0;
    printf("%d\n", ans);
    mask ^= ans;
}

void Add() {
    get(); REP_S(cc, s) Ext(c);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    NIL = new node(); NIL->reset(0); REP(i, N) T[i] = &TPool[i];
    int Q; RD(Q); Init(); DO(Q) {
        RS(s); if (s[0] == 'Q') {
            Query();
        } else {
            Add();
        }
    }
}