【HNOI2016模拟4.4】Alphadog

Description

n<=1e5,字元集大小<=26

Solution

我們把原串的回文樹建出來，以下讨論的都是fail樹

設X為x這個字元在回文樹上所對應的點

Y為y這個字元在回文樹上所對應的點

可以發現LCP(x,y)等價于LCA(X,Y)的長度

也就是我們要動态維護 ∑Xlen(LCA(X,Y))

先考慮N^2暴力

維護每個點的子樹中有多少個有用的回文串，設為siz[x]

那麼x這個點的父親對答案的貢獻就是len(fa[x])*(siz[fa[x]]-siz[x])

可是這樣也很難維護，怎麼辦呢

我們可以類似差分的思想，設 val[x]=len(x)−len(fa[x])

那麼答案就是y到根路徑上的 ∑val[x]∗siz[x]

觀察到val是不變的，siz每次隻會修改一條到根的路徑

于是我們可以用LCT來維護這個東西

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct palindrome_tree{int len,fail,to[27];}tr[N];
int n,sig,tot,last,st[N];
int t[N][2],f[N],p[N],key[N],lazy[N],d[N],size[N],ca[N];
ll c,ans,sum[N],an[N],cnt[N];
void updata(int x) {
    size[x]=size[t[x][0]]+size[t[x][1]]+1;
    sum[x]=sum[t[x][0]]+sum[t[x][1]]+key[x];
    cnt[x]=cnt[t[x][0]]+cnt[t[x][1]]+ca[x];
    an[x]=an[t[x][0]]+an[t[x][1]]+(ll)key[x]*ca[x];
}
void modify(int x,int y) {
    ca[x]+=y;
    cnt[x]+=(ll)y*size[x];
    an[x]+=(ll)y*sum[x];
    lazy[x]+=y;
}
void down(int x) {
    if (lazy[x]) {
        modify(t[x][0],lazy[x]);
        modify(t[x][1],lazy[x]);
        lazy[x]=0;
    }
}
void remove(int x,int y) {
    do {
        d[++d[0]]=x;
        x=f[x];
    } while (x!=y);
    while (d[0]) down(d[d[0]--]);
}
int son(int x) {return t[f[x]][1]==x;}
void rotate(int x) {
    int y=f[x],z=son(x);f[x]=f[y];
    if (f[x]) t[f[x]][son(y)]=x;
    else p[x]=p[y],p[y]=0;
    if (t[x][1-z]) f[t[x][1-z]]=y;
    t[y][z]=t[x][1-z];t[x][1-z]=y;f[y]=x;
    updata(y);updata(x);
}
void splay(int x,int y) {
    remove(x,y);
    while (f[x]!=y) {
        if (f[f[x]]!=y)
            if (son(x)==son(f[x])) rotate(f[x]);
            else rotate(x);
        rotate(x);
    }
}
void access(int x) {
    int y=0;
    while (x) {
        splay(x,0);
        f[t[x][1]]=0;p[t[x][1]]=x;
        t[x][1]=y;f[y]=x;p[y]=0;
        updata(x);
        y=x;x=p[x];
    }
}
void link(int x,int y) {p[x]=y;}
int get(int n,int x) {
    while (st[n-tr[x].len-1]!=st[n]) x=tr[x].fail;
    return x;
}
void add(int n,int x) {
    int now=get(n,last);
    if (!tr[now].to[x]) {
        tr[++tot].len=tr[now].len+2;
        tr[tot].fail=tr[get(n,tr[now].fail)].to[x];
        tr[now].to[x]=tot;

        int fa=tr[tot].fail;
        key[tot+1]=tr[tot].len-tr[fa].len;
        if (fa==0) fa=2;
        else if (fa>1) fa++;
        link(tot+1,fa);
    }
    last=tr[now].to[x];
}
int main() {
    scanf("%d%d",&n,&sig);
    tr[++tot].len=-1;
    tr[0].len=0;tr[0].fail=1;
    link(2,1);
    fo(i,1,n) {
        scanf("%lld",&c);
        if (sig) c^=ans;c++;
        st[i]=c;add(i,c);
        int x=last;
        if (x==0) x=2;
        else if (x>1) x++;
        access(x);splay(x,0);
        modify(x,1);ans+=an[x];
        printf("%lld\n",ans);
    }
}