P16693 Tokitsukaze and Palindrome Border

tokitsukaze · 2026-08-04 17:00:13 · 题解

我在 19 年学习回文自动机（PAM）时，想造一个只能使用 PAM 的 fail 树性质做的题，这个题就是当时的产物。

本题曾经投稿到了 20 年的 hdu 多校，但由于发现好像可以使用 Trie + manachar/hash 替代 PAM，觉得太糖了，于是就把这题下了。换上去一个，和当时著名毒瘤出题人 Claris 一起现编的，可能真的只能用 PAM 的回文题，这个题。

之后，本题投稿到了 22 年 Codeforces Round 789 中，coordination 是后来臭名昭著的 74TrAkToR。后来由于另一个出题人掏出了一个数据结构题，题型上比较相似，于是把这题换下来了。

后来 23 年年底的时候，听说 ECF 缺投，于是尝试投了一下。果不其然，被杜老师毙了，评价是，不太喜欢（所以 74TrAkToR 说这题是 good task 是不是糖完了.jpg）。

后来就不知道该把这题丢哪了，寻思，要不，就丢在洛谷上，然后在暑假集训里，夹带私货.jpg

Solution

这题做法应该不少，目前已知有根号做法，以及 74TrAkToR 说能够做到单 \log（但我翻不到他的验题记录了.jpg）。

这里只说一下 std 的做法。

前置知识：回文自动机，轻重链剖分，线段树。

Part 1

先考虑只有两个串 s 和 t 时，如何求 f(s,t)。

令 \operatorname{rev}(s) 表示字符串 s 的反转串。那么 \operatorname{pre}(s, len) = \operatorname{suf}(t, len) 这个条件可以转化为：\operatorname{pre}(s, len) = \operatorname{pre}(\operatorname{rev}(t), len)。

现在问题变为，求 s 和 \operatorname{rev}(t) 的所有公共回文前缀长度之和。

PAM 中，每个节点代表一个回文串。令 \operatorname{end}(s) 表示字符串 s 插入进 PAM 时，插入最后一个字符后，在 PAM 上的节点。那么 s 的所有回文前缀，其实就是在 PAM 的 fail 树中，\operatorname{end}(s) 的所有祖先节点。

在 PAM 的每个节点带上一个回文串的长度 len。所以最后变成，求在 fail 树上，\operatorname{end}(s) 与 \operatorname{end}(\operatorname{rev}(t)) 到根节点的路径交集上的所有节点的 len 之和。

Part 2

回到题目，多串的情况，将所有 s 和 \operatorname{rev}(s) 插入同一个 PAM，先把 fail 树建出来。由于是在树上操作，并且有多次询问，考虑使用树剖配合线段树来维护。

对于 s 和 \operatorname{rev}(s)，开两个线段树来分别维护树上每个节点经过的次数：

• Tree 0：维护所有 s_i 在 fail 树上 \operatorname{end}(s_i) 到根路径每个节点的经过次数。
• Tree 1：维护所有 \operatorname{rev}(s_i) 在 fail 树上 \operatorname{end}(\operatorname{rev}(s_i)) 到根路径每个节点的经过次数。

当我们向已有的字符串集合中加入一个字符串 s_k 时，它会产生两部分贡献：

1. 作为前缀： 向 Tree 0 中的 \operatorname{end}(s_k) 到根的路径加上 1；同时去 Tree 1 中查询 \operatorname{end}(s_k) 到根的路径上的权值和，这部分代表它与已有的所有字符串的后缀匹配产生的值，将其计入答案。
2. 作为后缀： 向 Tree 1 中的 \operatorname{end}(\operatorname{rev}(s_k)) 到根的路径加上 1；同时去 Tree 0 中查询 \operatorname{end}(\operatorname{rev}(s_k)) 到根的路径上的权值和，这部分代表它与已有的所有字符串的前缀匹配产生的值，将其计入答案。

线段树怎么维护就不详细展开了，就大概是维护一个区间的 len 之和：sumlen。然后区间出现次数 +1，其实就是这个区间 val+sumlen，tag+1。

Part 3

我们先通过上述方式计算出没有串被禁用时的答案。

每次询问时，对被禁用掉的每个串，通过上述的方式撤销贡献，计算完答案之后，再加入回去。

于是就，做完了。

时间复杂度 O((n+ \sum k) \log^2(\sum|s|))。

Code

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const int MAX=4e5+10;
ll bit[MAX],val[MAX];
struct Segment_Tree
{
    #define type ll
    #define ls (id<<1)
    #define rs (id<<1|1)
    int n,ql,qr;
    type a[MAX],v[MAX<<2],tag[MAX<<2],qv;
    void pushup(int id)
    {
        v[id]=v[ls]+v[rs];
    }
    void pushdown(int l,int r,int id)
    {
        if(!tag[id]) return;
        int mid=(l+r)>>1;
        v[ls]+=tag[id]*(bit[mid]-bit[l-1]);
        v[rs]+=tag[id]*(bit[r]-bit[mid]);
        tag[ls]+=tag[id];
        tag[rs]+=tag[id];
        tag[id]=0;
    }
    void build(int l,int r,int id)
    {
        tag[id]=0;
        v[id]=0;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,ls);
        build(mid+1,r,rs);
        pushup(id);
    }
    void update(int l,int r,int id)
    {
        if(l>=ql&&r<=qr)
        {
            v[id]+=(bit[r]-bit[l-1])*qv;
            tag[id]+=qv;
            return;
        }
        pushdown(l,r,id);
        int mid=(l+r)>>1;
        if(ql<=mid) update(l,mid,ls);
        if(qr>mid) update(mid+1,r,rs);
        pushup(id);
    }
    type res;
    void query(int l,int r,int id)
    {
        if(l>=ql&&r<=qr)
        {
            res+=v[id];
            return;
        }
        pushdown(l,r,id);
        int mid=(l+r)>>1;
        if(ql<=mid) query(l,mid,ls);
        if(qr>mid) query(mid+1,r,rs);
    }
    void build(int _n){n=_n;build(1,n,1);}
    void upd(int l,int r,type v)
    {
        ql=l;
        qr=r;
        qv=v;
        update(1,n,1);
    }
    type ask(int l,int r)
    {
        ql=l;
        qr=r;
        res=0;
        query(1,n,1);
        return res;
    }
    #undef type
    #undef ls
    #undef rs
}tr[2];
struct Heavy_Light_Decomposition
{
    #define type ll
    struct edge{int a,b;type v;};
    vector<int> mp[MAX];
    vector<edge> e;
    int dep[MAX],fa[MAX],sz[MAX],son[MAX];
    int id[MAX],top[MAX],dfn[MAX],tot;
    int n,rt;
    void init(int _n)
    {
        n=_n;
        for(int i=0;i<=n;i++) mp[i].clear();
        e.clear();
        e.push_back({0,0,0});
    }
    void add_edge(int a,int b,type v=0)
    {
        e.push_back({a,b,v});
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    void dfs1(int x,int pre,int h)
    {
        int i,to;
        dep[x]=h;
        fa[x]=pre;
        sz[x]=1;
        for(i=0;i<mp[x].size();i++)
        {
            to=mp[x][i];
            if(to==pre) continue;
            dfs1(to,x,h+1);
            sz[x]+=sz[to];
            if(son[x]==-1||sz[to]>sz[son[x]]) son[x]=to;
        }
    }
    void dfs2(int x,int tp)
    {
        int i,to;
        dfn[x]=++tot;
        id[dfn[x]]=x;
        top[x]=tp;
        if(son[x]==-1) return;
        dfs2(son[x],tp);
        for(i=0;i<mp[x].size();i++)
        {
            to=mp[x][i];
            if(to!=son[x]&&to!=fa[x]) dfs2(to,to);
        }
    }
    void work(int _rt)
    {
        rt=_rt;
        for(int i=0;i<=n;i++) son[i]=-1;
        tot=0;
        dfs1(rt,0,0);
        dfs2(rt,rt);
    }
    void init_node()
    {
        int i;
        for(i=1;i<=n;i++) bit[dfn[i]]=val[i];
        for(i=1;i<=n;i++) bit[i]+=bit[i-1];
        tr[0].build(n);
        tr[1].build(n);
    }
    void modify_node(int x,int y,type val,int f)
    {  
        while(top[x]!=top[y])
        {  
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            tr[f].upd(dfn[top[x]],dfn[x],val);
            x=fa[top[x]];
        }  
        if(dep[x]>dep[y]) swap(x,y);
        tr[f].upd(dfn[x]+1,dfn[y],val);
    }
    type query_node(int x,int y,int f)
    {  
        type res=0;
        while(top[x]!=top[y])
        {  
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            res+=tr[f].ask(dfn[top[x]],dfn[x]);
            x=fa[top[x]];
        }  
        if(dep[x]>dep[y]) swap(x,y);
        res+=tr[f].ask(dfn[x]+1,dfn[y]);
        return res;
    }
    #undef type
}hld;
struct Palindrome_Tree
{
    int len[MAX],nex[MAX][26],fail[MAX],last,s[MAX],tot,n;
    int deep[MAX];
    int newnode(int l)
    {
        memset(nex[tot],0,sizeof nex[tot]);
        fail[tot]=0; 
        deep[tot]=0;
        len[tot]=l;
        return tot++;
    }
    void init()
    {
        tot=n=last=0;
        newnode(0);
        newnode(-1);
        s[0]=-1;
        fail[0]=1;
    }
    int get_fail(int x)
    {
        while(s[n-len[x]-1]!=s[n]) x=fail[x];
        return x;
    }
    void add(int t)//attention the type of t is int
    {
        int id,now;
        s[++n]=t;
        now=get_fail(last);
        if(!nex[now][t])
        {
            id=newnode(len[now]+2);
            fail[id]=nex[get_fail(fail[now])][t];
            deep[id]=deep[fail[id]]+1;
            nex[now][t]=id;
        }
        last=nex[now][t];
    }
    int insert(char *a,int f)
    {
        n=last=0;
        s[0]=-1;
        int len=strlen(a);
        for(int i=0;i<len;i++) add(a[i]-'a');
        return last;
    }
    void build_tree()// root is 0
    {
        val[0]=0;
        for(int i=1;i<tot;i++)
        {
            hld.add_edge(fail[i]+1,i+1);
            val[i+1]=len[i];
        }
    }
}pam;
/*
pam.init();
pam.add(t,id); t is int
*/
int last_pos[MAX][2];
int qst[MAX];
char s[MAX];
int main()
{
    int n,i,rt,k,q;
    ll ans,now;
    scanf("%d",&n);
    pam.init();
    for(i=1;i<=n;i++)
    {
        scanf("%s",s);
        last_pos[i][0]=pam.insert(s,0)+1;
        reverse(s,s+strlen(s));
        last_pos[i][1]=pam.insert(s,1)+1;
    }
    hld.init(pam.tot);
    pam.build_tree();
    rt=1;
    hld.work(rt);
    hld.init_node();
    now=0;
    for(i=1;i<=n;i++)
    {
        hld.modify_node(rt,last_pos[i][0],1,0);
        now+=hld.query_node(rt,last_pos[i][0],1);
        hld.modify_node(rt,last_pos[i][1],1,1);
        now+=hld.query_node(rt,last_pos[i][1],0);
    }
    scanf("%d",&q);
    while(q--)
    {
        ans=now;
        scanf("%d",&k);
        for(i=1;i<=k;i++)
        {
            scanf("%d",&qst[i]);
            ans-=hld.query_node(rt,last_pos[qst[i]][0],1);
            hld.modify_node(rt,last_pos[qst[i]][0],-1,0);
            ans-=hld.query_node(rt,last_pos[qst[i]][1],0);
            hld.modify_node(rt,last_pos[qst[i]][1],-1,1);
        }
        for(i=1;i<=k;i++)
        {
            hld.modify_node(rt,last_pos[qst[i]][0],1,0);
            hld.modify_node(rt,last_pos[qst[i]][1],1,1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

:::