P4770 [NOI2018] 你的名字

AC Code

#include<bits/stdc++.h>
#define o____________________ for
#define i_______________________ return
#define i__________________________ int
#define i_________________________ {
#define ll long long
#define ls tr[____________].li
#define rs tr[____________].ri
using namespace std;
const i__________________________ INF=0x3f3f3f3f,N=5e5+5,MT=4e7+5;
i__________________________ n,L,R;
char s[N],t[N];
i__________________________ ha[N];
struct vector_xds
i_________________________
i__________________________ li, ri;
i__________________________ _____________;
}tr[MT];
i__________________________ root[N<<1],____[N],tcnt=0;
void ________________(i__________________________ &____________,i__________________________ l,i__________________________ r,i__________________________ id)
i_________________________
____________=++tcnt;
tr[____________]._____________=-1;
if(l==r)
i_________________________
tr[____________]._____________=l;
i_______________________;
}
i__________________________ mid=(l+r)>>1;
if(id<=mid)
________________(ls,l,mid,id);
else
________________(rs,mid+1,r,id);
tr[____________]._____________=max(tr[ls]._____________,tr[rs]._____________);
}
i__________________________ __________________(i__________________________ x,i__________________________ y,i__________________________ l,i__________________________ r)
i_________________________
if(!x||!y)
i_______________________ x+y;
if(l==r)
i_________________________
tr[x]._____________+=tr[y]._____________;
i_______________________ x;
}
i__________________________ mid=(l+r)>>1,z=++tcnt;
tr[z].li=__________________(tr[x].li,tr[y].li,l,mid);
tr[z].ri=__________________(tr[x].ri,tr[y].ri,mid+1,r);
tr[z]._____________=max(tr[x]._____________,tr[y]._____________);
i_______________________ z;
}
i__________________________ _________________(i__________________________ ____________,i__________________________ l,i__________________________ r,i__________________________ L,i__________________________ R)
i_________________________
if(!____________)
i_______________________ -1;
if(l==L&&r==R)
i_______________________ tr[____________]._____________;
i__________________________ mid=(l+r)>>1;
if(R<=mid)
i_______________________ _________________(ls,l,mid,L,R);
else if(L>mid)
i_______________________ _________________(rs,mid+1,r,L,R);
else
i_______________________ max(_________________(ls,l,mid,L,mid),_________________(rs,mid+1,r,mid+1,R));
}
struct SAM
i_________________________
i__________________________ cnt,___________;
i__________________________ ________[N<<1][27],len[N<<1],______[N<<1];
void __()
i_________________________
______[cnt=___________=0]=-1;//
memset(________[0],0,sizeof(________[0]));
}
void _______(i__________________________ c, i__________________________ id)
i_________________________
i__________________________ ____________=++cnt,_____=___________;//
memset(________[cnt],0,sizeof(________[cnt]));
len[____________]=len[___________]+1;
while(_____!=-1&&!________[_____][c])
i_________________________
________[_____][c]=____________;
_____=______[_____];
}
if(_____==-1)
______[____________]=0;
else
i_________________________
i__________________________ q=________[_____][c];
if(len[q]==len[_____]+1)
______[____________]=q;
else
i_________________________
i__________________________ __________=++cnt;//
memset(________[cnt],0,sizeof(________[cnt]));
memcpy(________[__________],________[q],sizeof(________[q]));
len[__________]=len[_____]+1;
______[__________]=______[q];
______[q]=______[____________]=__________;
while(_____!=-1&&________[_____][c]==q)
i_________________________
________[_____][c]=__________;
_____=______[_____];
}
}
}
___________=____________;
if(id)
____[id]=____________;
}
i__________________________ _____os[N<<1],___[N<<1];
void _()
i_________________________
o____________________(i__________________________ i=1;i<=cnt;i++)
++___[len[i]];
o____________________(i__________________________ i=1;i<=cnt;i++)
___[i]+=___[i-1];
o____________________(i__________________________ i=1;i<=cnt;i++)
_____os[___[len[i]]--]=i;
o____________________(i__________________________ i=cnt;i>=1;i--)
i_________________________
i__________________________ ____________=_____os[i],fa=______[____________];
root[fa]=__________________(root[fa],root[____________],0,n-1);
}
}
ll calc(char s[])
i_________________________
ll ret=0;
i__________________________ m=strlen(s);
o____________________(i__________________________ i=0,l=0,_____=0,_____os=0;i<m;i++)
i_________________________
i__________________________ c=s[i]-'a';
while(_____!=-1&&(!________[_____][c]||(_____os=_________________(root[________[_____][c]],0,n-1,L,R))==-1))
i_________________________
_____=______[_____];
l=len[_____];
}
if(_____==-1)
_____=l=0;
else
i_________________________
l++;
_____=________[_____][c];
i__________________________ t_____=min(l,_____os-L+1);
if(t_____>ha[i])
ret+=t_____-ha[i];
if(l>_____os-L+1)
i_________________________
i__________________________ t_____3=max(t_____,ha[i]),q=______[_____],l2=len[q];
while(q)
i_________________________
i__________________________ _____os2=_________________(root[q],0,n-1,L,R),t_____2=min(l2,_____os2-L+1);
if(t_____2>t_____3)
ret+=t_____2-t_____3;
else if(l2<=_____os2-L+1)
break; 
q=______[q];
l2=len[q];
t_____3=max(t_____2,ha[i]);
}
}
}
}
i_______________________ ret;
}
}S,T;
i__________________________ main()
i_________________________
i__________________________ m;
scanf("%s",s);
n=strlen(s);
S.__();
o____________________(i__________________________ i=0;i<n;i++)
i_________________________
S._______(s[i]-'a',i);
________________(root[____[i]],0,n-1,i);
}
S._();
scanf("%d",&m);
o____________________(i__________________________ i=1;i<=m;i++)
i_________________________
scanf("%s",t);
i__________________________ len=strlen(t);
T.__();
o____________________(i__________________________ j=0;j<len;j++)
i_________________________
T._______(t[j]-'a',-1);
ha[j]=T.len[T.______[T.___________]];
}
scanf("%d%d",&L,&R);
L--;
R--;
ll t_____=0;
o____________________(i__________________________ j=0;j<len;j++)
t_____+=j+1-ha[j];
printf("%lld\n",t_____-S.calc(t));
}
i_______________________ 0;
}