题解：P16693 Tokitsukaze and Palindrome Border
zyn0309
·
·
题解
\text{Link}
时老师的做法太变态了。
思路
对于所有 s，我们用随便什么你喜欢的方法可以线性找出所有回文前缀（我用的是哈希）。
把 s 插入字典树，对字典树上所有代表回文串的节点打上一个标记。对 s 的反串也这样做一遍。同时记录一下 pos1_i 和 pos2_i 代表第 i 个字符串的最长回文前缀或后缀对应字典树上的哪个节点。
发现每个串大概是对 pos1 和 pos2 的到根链上的回文串有贡献，那么我们先把这个字典树缩成只有回文节点的样子。具体就是把每个回文节点跟它祖先离它最近的回文节点连边（我们认为字典树的根也是回文节点）。
禁用相当于我们要支持到根链修改 $cnt$，维护答案。对于字典树树剖，线段树区间维护 $\sum_{i=l}^r dep_i \times cnt1_i \times cnt2_i$，$\sum_{i=l}^r dep_i \times cnt1_i$，$\sum_{i=l}^r dep_i \times cnt2_i$，$\sum_{i=l}^r dep_i$，打标记即可修改。
时间复杂度 $O((n+\sum k)\log^2 (\sum |s|))$，常数挺小的。
## Code
```cpp
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb emplace_back
using namespace std;
const int N=6e5+10;
const ull pp=13331;
int n,q,tot=1,pos1[N],pos2[N],fa[N],cnt1[N],cnt2[N],dis[N],siz[N],son[N],top[N],dfn[N],w[N];
vector<int>e[N];
ull p[N],ha[N];
inline ull getval(int l,int r){return ha[r]-ha[l-1]*p[r-l+1];}
string s;
bitset<N>ok;
struct trie{
int ch[26];
bool ok;
}T[N];
inline int add(){
int u=1,pos=1;
for(int i=1;i<(int)s.size();++i){
int to=s[i]-'a';
if(!T[u].ch[to])T[u].ch[to]=++tot,dis[tot]=dis[u]+1;
u=T[u].ch[to];
if(ok[i])T[u].ok=1,pos=u;
}
return pos;
}
inline void dfs(int u,int last){
if(T[u].ok){
fa[u]=last;
e[last].pb(u);
last=u;
}
for(int i=0;i<26;++i){
if(T[u].ch[i])
dfs(T[u].ch[i],last);
}
}
inline void dfs1(int u){
siz[u]=1;
for(int v:e[u]){
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
inline void dfs2(int u,int tt){
top[u]=tt;
dfn[u]=++tot;
w[tot]=u;
if(!son[u])return;
dfs2(son[u],tt);
for(int v:e[u]){
if(v==son[u])continue;
dfs2(v,v);
}
}
struct tree{
int l,r;
ll ans,dep,cnt1,cnt2,lazy1,lazy2;
#define lson(u) (u<<1)
#define rson(u) (u<<1|1)
}t[N<<2];
inline void push_up(int u){
t[u].cnt1=t[lson(u)].cnt1+t[rson(u)].cnt1;
t[u].cnt2=t[lson(u)].cnt2+t[rson(u)].cnt2;
t[u].ans=t[lson(u)].ans+t[rson(u)].ans;
}
inline void build(int u,int l,int r){
t[u].l=l;
t[u].r=r;
if(l==r){
t[u].dep=dis[w[l]];
return;
}
int mid=(l+r)>>1;
build(lson(u),l,mid);
build(rson(u),mid+1,r);
t[u].dep=t[lson(u)].dep+t[rson(u)].dep;
}
inline void work1(int u,ll val){
t[u].ans+=val*t[u].cnt2;
t[u].cnt1+=val*t[u].dep;
t[u].lazy1+=val;
}
inline void work2(int u,ll val){
t[u].ans+=val*t[u].cnt1;
t[u].cnt2+=val*t[u].dep;
t[u].lazy2+=val;
}
inline void push_down(int u){
work1(lson(u),t[u].lazy1);
work2(lson(u),t[u].lazy2);
work1(rson(u),t[u].lazy1);
work2(rson(u),t[u].lazy2);
t[u].lazy1=t[u].lazy2=0;
}
inline void update1(int u,int l,int r,int val){
if(l<=t[u].l&&t[u].r<=r){
work1(u,val);
return;
}
push_down(u);
int mid=(t[u].l+t[u].r)>>1;
if(l<=mid)update1(lson(u),l,r,val);
if(r>mid)update1(rson(u),l,r,val);
push_up(u);
}
inline void update2(int u,int l,int r,int val){
if(l<=t[u].l&&t[u].r<=r){
work2(u,val);
return;
}
push_down(u);
int mid=(t[u].l+t[u].r)>>1;
if(l<=mid)update2(lson(u),l,r,val);
if(r>mid)update2(rson(u),l,r,val);
push_up(u);
}
inline void push1(int u,int val){
while(u){
update1(1,dfn[top[u]],dfn[u],val);
u=fa[top[u]];
}
}
inline void push2(int u,int val){
while(u){
update2(1,dfn[top[u]],dfn[u],val);
u=fa[top[u]];
}
}
signed main(){
cin>>n;
p[0]=1;
for(int i=1;i<N;++i)p[i]=p[i-1]*pp;
for(int i=1;i<=n;++i){
cin>>s;
int len=s.size();
s=' '+s;
for(int j=1;j<=len;++j)ha[j]=ha[j-1]*pp+s[len-j+1];
ull now=0;
for(int j=1;j<=len;++j){
now=now*pp+s[j];
ok[j]=now==getval(len-j+1,len);
}
pos1[i]=add();
for(int j=1;j<=(len>>1);++j)swap(s[j],s[len-j+1]);
for(int j=1;j<=len;++j)ha[j]=ha[j-1]*pp+s[len-j+1];
now=0;
for(int j=1;j<=len;++j){
now=now*pp+s[j];
ok[j]=now==getval(len-j+1,len);
}
pos2[i]=add();
}
dfs(1,1);
tot=0;
dfs1(1);
dfs2(1,1);
build(1,1,tot);
for(int i=1;i<=n;++i)push1(pos1[i],1),push2(pos2[i],1);
cin>>q;
int k;
while(q--){
cin>>k;
vector<int>del(k);
for(int i=0;i<k;++i){
cin>>del[i];
push1(pos1[del[i]],-1);
push2(pos2[del[i]],-1);
}
cout<<t[1].ans<<"\n";
for(int i=0;i<k;++i){
push1(pos1[del[i]],1);
push2(pos2[del[i]],1);
}
}
return 0;
}
```