[Str记录]HDU5421 Victor and String

command_block · 2021-01-22 19:19:50 · 个人记录

题意 ：维护一个字符串 s ，支持 ：

• 在前端插入字符。

• 在后端插入字符。

• 查询本质不同回文串个数。

• 查询位置不同回文串个数。

多组数据，T\leq 5,\ n\leq 10^5 ，时限\texttt{1s}。

配合 回文自动机小记 食用。

双向插入 \rm PAM 的板子。

#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
struct Node
{int t[26],f,len,dep;}a[MaxN];
int tn,lasr,lasl,tlen;ll sum;
char str[MaxN<<1];
void insl(int k,char c)
{
  int p=lasl;
  while(str[k+a[p].len+1]!=c)p=a[p].f;
  if (!a[p].t[c]){
    int np=lasl=++tn,v;
    for(v=a[p].f;str[k+a[v].len+1]!=c;v=a[v].f);
    if (!a[v].t[c])a[np].f=2;
    else a[np].f=a[v].t[c];
    a[a[p].t[c]=np].len=a[p].len+2;
    a[np].dep=a[a[np].f].dep+1;
  }else lasl=a[p].t[c];
  sum+=a[lasl].dep;
  if (a[lasl].len==tlen)lasr=lasl;
}
void insr(int k,char c)
{
  int p=lasr;
  while(str[k-a[p].len-1]!=c)p=a[p].f;
  if (!a[p].t[c]){
    int np=lasr=++tn,v;
    for(v=a[p].f;str[k-a[v].len-1]!=c;v=a[v].f);
    if (!a[v].t[c])a[np].f=2;
    else a[np].f=a[v].t[c];
    a[a[p].t[c]=np].len=a[p].len+2;
    a[np].dep=a[a[np].f].dep+1;
  }else lasr=a[p].t[c];
  sum+=a[lasr].dep;
  if (a[lasr].len==tlen)lasl=lasr;
}
void Init(){
  memset(a,0,sizeof(Node)*(tn+2));
  a[1].len=-1;a[1].f=a[2].f=1;
  tn=lasl=lasr=2;sum=tlen=0;
}
int n;char buf[5];
void solve()
{
  int tl=n+1,tr=n;
  memset(str,-1,sizeof(str));
  Init();
  for (int i=1,op;i<=n;i++){
    scanf("%d",&op);
    if (op==1){
      tlen++;
      scanf("%s",buf);
      str[--tl]=(buf[0]-='a');
      insl(tl,str[tl]);
    }else if (op==2){
      tlen++;
      scanf("%s",buf);
      str[++tr]=(buf[0]-='a');
      insr(tr,str[tr]);
    }else if (op==3)printf("%d\n",tn-2);
    else printf("%lld\n",sum);
  }
}
int main()
{
  while(~scanf("%d",&n))solve();
  return 0;
}