【HNOI2016模擬4.4】Alphadog

【HNOI2016模擬4.4】Alphadog

Description

這裡寫圖片描述
n<=1e5,字符集大小<=26

Solution

我們把原串的迴文樹建出來,以下討論的都是fail樹
設X為x這個字元在迴文樹上所對應的點
Y為y這個字元在迴文樹上所對應的點
可以發現LCP(x,y)等價於LCA(X,Y)的長度
也就是我們要動態維護∑Xlen(LCA(X,Y))\sum_{X}len(LCA(X,Y))
先考慮N^2暴力
維護每個點的子樹中有多少個有用的迴文串,設為siz[x]
那麼x這個點的父親對答案的貢獻就是len(fa[x])*(siz[fa[x]]-siz[x])
可是這樣也很難維護,怎麼辦呢
我們可以類似差分的思想,設val[x]=len(x)−len(fa[x])val[x]=len(x)-len(fa[x])
那麼答案就是y到根路徑上的∑val[x]∗siz[x]\sum_{}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);
}
}