CCPC2025JinanI.cpp

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int N = 1e6+10, K = 22;

struct PAM {
    int tot;  // string size
    int idx;  // pam size
    int last;
    int fail[N], tr[N][26], len[N], dep[N];
    int fa[N][K];
    char s[N];

    int deprev[N];

    int create(int l) {
        idx++;
        memset(tr[idx], 0, sizeof tr[idx]);
        memset(fa[idx], 0, sizeof fa[idx]);
        len[idx] = l;
        fail[idx] = 0;

        deprev[idx] = 0;
        dep[idx] = 0;

        return idx;
    }

    void init() {
        idx = -1;
        last = 0;
        s[tot = 0] = '$';
        create(0);
        create(-1);
        fail[0] = 1;
    }

    int getfail(int x) {
        while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
        return x;
    }

    void insert(char ch) {
        s[++tot] = ch;
        int now = getfail(last);
        int p = ch - 'a';
        if (!tr[now][p]) {
            int x = create(len[now] + 2);
            fail[x] = tr[getfail(fail[now])][p];
            
            if (len[x] >= 3) {
                deprev[x] = deprev[fail[x]] + 1;
                
                if (len[fail[x]] >= 3) {
                    dep[x] = dep[fail[x]] + (s[tot-len[fail[x]]+1] == s[tot-len[fail[x]]]);
                }
                else {
                    dep[x] = dep[fail[x]];
                }
            }
            else {
                deprev[x] = deprev[fail[x]];
                dep[x] = dep[fail[x]];
                assert(deprev[x] == 0);
                assert(dep[x] == 0);
            }

            tr[now][p] = x;
            
            fa[x][0] = fail[x];
            for (int k = 1; k < K; k++) fa[x][k] = fa[fa[x][k-1]][k-1];
        }
        last = tr[now][p];
    }

    int upd(int mxlen) {
        int u = last;
        if (len[u] >= mxlen) {
            for (int k = K-1; k >= 0; k--) {
                if (len[fa[u][k]] >= mxlen) {
                    u = fa[u][k];
                }
            }
            u = fa[u][0];
        }

        if (len[u] >= 3) return dep[u] + (s[tot-len[u]+1] == s[tot-len[u]]);
        return dep[u];
    }

    int updrev(int mxlen) {
        int u = last;
        if (len[u] > mxlen) {
            for (int k = K-1; k >= 0; k--) {
                if (len[fa[u][k]] > mxlen) {
                    u = fa[u][k];
                }
            }
            u = fa[u][0];
        }
        return deprev[u];
    }
} p, rp;

char type[N];

void solve() {
    string s;
    cin >> s;
    int n = s.size(), m;
    cin >> m;

    p.init();
    rp.init();
    string op, pre, suf;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op[0] == 'R') suf += op[1], type[i] = 'R';
        else pre += op[1], type[i] = 'L';
    }

    // build pam
    for (auto it = pre.rbegin(); it != pre.rend(); it++) p.insert(*it);

    i64 ans = 0;
    int len = 0;
    for (char c: s) {
        p.insert(c);
        ans += p.upd(++len);
    }

    for (auto it = suf.rbegin(); it != suf.rend(); it++) rp.insert(*it);
    for (auto it = s.rbegin(); it != s.rend(); it++) rp.insert(*it);

    int L = pre.size() + 1, R = pre.size() + s.size();
    int l = 0, r = 0;

    cout << ans << ' ';
    for (int i = 1; i <= m; i++) {
        if (type[i] == 'R') {
            p.insert(suf[r++]);
            ans += p.upd((R+r) - (L-l) + 1);
        }
        else {
            if (pre[l] == rp.s[rp.tot]) {
                ans += rp.updrev((R+r) - (L-l) + 1);
            }
            rp.insert(pre[l++]);
        }
        cout << ans << " \n"[i == m];
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}