某島

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

BZOJ 3879. SvT

SAM + 虛樹。
看起來可以重鏈剖分簡化 lca 代碼! https://www.cnblogs.com/cjyyb/p/10185462.html

const int N = int(1e6) + 9, C = 26, LV = 21;

int Q;

namespace SAM {

    int trans[N][C], fail[N], len[N], tail, tot;
    VI adj[N]; int dfn[N], lfn[N], dep[N], fa[LV][N];
    char str[N/2]; int pos[N/2], n;

    inline int new_node(){
        RST(trans[tot]); tail = tot;
        return tot++;
    }

    inline int new_node(int u){
        CPY(trans[tot], trans[u]); fail[tot] = fail[u];
        return tot++;
    }

    inline int move_up(int x, int t){
        for (int lv=0;t;++lv,t>>=1)
            if (t&1) x = fa[lv][x];
        return x;
    }
    inline int lca(int x, int y) {
        if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
        DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
        return fa[0][x];
    }
    inline bool cmp(int a, int b) {
        return dfn[a] < dfn[b];
    }

#define v trans[u]
#define f fail[u]
#define ff fail[uu]

    int Ext(int c){
        int u = tail, uu = new_node(); len[uu] = len[u] + 1;
        while (u && !v) v = uu, u = f;
        if (!u && !v) v = uu, ff = 0;
        else{
            if (len[v] == len[u] + 1) ff = v;
            else{
                int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
                fail[_v] = ff = vv;
                while (v == _v) v = vv, u = f;
            }
        }
        return tail;
    }
#undef v
#define v (*it)
    void dfs(int u = 0) {
        dfn[u] = ++n;
        ECH(it, adj[u]) {
            dep[v] = dep[u] + 1;
            fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
            dfs(v);
        }
        lfn[u] = n;
    }

    void Init(){
        tot = 0, tail = new_node(); RD(n, Q);
        RS(str); DWN(i, n, 0) pos[i+1] = Ext(str[i]-'a');
        FOR(u, 1, tot) adj[f].PB(u); n = 0; dfs();
    }
#undef f
#undef ff
} // using namespace SAM;


namespace VT {
    VI adj[N]; VI T; int sta[N], top;
    int f[N]; LL z;

    void dfs(int u = T[0]) {
        ECH(it, adj[u]) {
            dfs(v);
            z += (LL) f[u] * f[v] * SAM::len[u];
            f[u] += f[v];
        }
    }
    void clean(int u = T[0]) {
        ECH(it, adj[u]) {
            clean(v);
        }
        f[u] = 0; adj[u].clear();
    }
    void Gao() {
        Rush {
            int t = SAM::pos[RD()]; f[t] = 1;
            T.PB(t);
        }
        UNQ(T, SAM::cmp); DWN(i, SZ(T)-1, 0) T.PB(SAM::lca(T[i], T[i+1]));
        UNQ(T, SAM::cmp); top = 0; ECH(it, T) {//for (auto u: T) {
            int u = *it;
            while (top && SAM::lfn[sta[top]] < SAM::dfn[u]) --top;
            if (top) adj[sta[top]].PB(u); sta[++top] = u;
        }

        z = 0; dfs(); printf("%lld\n", z);
        clean(); T.clear();
    }
} // using namespace VT;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    SAM::Init();
    DO(Q) VT::Gao();
}