题解:

后缀自动机

我们可以通过建立trie

把询问变成询问一些点的并

把trie建立成SAM和广义SAM基本相同,就是在父亲和儿子之间连边

然后就变成了询问树链的并

我们可以发现答案=sigma dis[i]  -sigma(dis[lca(i,i+1)])

其中i和i+1dfs序相邻

可以通过set来维护

***

把倍增的预处理写在了dfs前

把&&写成了&

代码:

#include <bits/stdc++.h>
#define rint register int
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define ll long long
using namespace std;
const int N=2e5;
char s[N];
int len,cnt,son[N][],pos[N],cnt2;
struct hz{
int ch[N][],node,len[N],fa[N];
hz()
{
node=;
}
int extend(int c,int z)
{
int lst=z;
int f=lst;
if (ch[f][c]&&len[ch[f][c]]==len[f]+)
{
lst=ch[f][c];
return(lst);
}
int p=++node; lst=p;
len[p]=len[f]+; //size[p][pl]=1;
while (f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
if (!f) { fa[p]=; return(p);};
int x=ch[f][c],y=++node;
if (len[f]+==len[x]) {fa[p]=x; node--;return(p);}
len[y]=len[f]+; fa[y]=fa[x]; fa[x]=fa[p]=y;
memcpy(ch[y],ch[x],sizeof(ch[x]));
while (f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
return(p);
}
void build(int x)
{
rep(i,,)
if (son[x][i])
{
pos[son[x][i]]=extend(i,pos[x]);
build(son[x][i]);
}
}
}S;
int l,head[N],bz[N][],dfn[N],rl[N],dis[N],fa[N],dep[N],zt[N];
struct re{
int a,b;
}a[N];
void arr(int x,int y)
{
a[++l].a=head[x];
a[l].b=y;
head[x]=l;
}
void dfs(int x,int y)
{
int u=head[x]; bz[x][]=y; dfn[x]=++cnt2; rl[cnt2]=x;
dep[x]=dep[y]+;
dis[x]=dis[y]+S.len[x]-S.len[y];
while (u)
{
int v=a[u].b;
dfs(v,x);
u=a[u].a;
}
}
set<int> M;
set<int>::iterator it;
int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
dep(i,,)
if (dep[bz[x][i]]>=dep[y]) x=bz[x][i];
if (x==y) return(x);
dep(i,,)
if (bz[x][i]!=bz[y][i]) x=bz[x][i],y=bz[y][i];
return(bz[x][]);
}
int main()
{
freopen("1.in","r",stdin);
freopen("3.out","w",stdout);
scanf("%s",s);
len=strlen(s);
int now=;
cnt=;
rep(i,,len-)
{
if (s[i]=='-') now=fa[now];
else
{
if (!son[now][s[i]-'a']) son[now][s[i]-'a']=++cnt,fa[cnt]=now;
now=son[now][s[i]-'a'];
}
}
pos[]=; S.build();
for(int i=;i<=S.node;i++) arr(S.fa[i],i);
dfs(,);
rep(i,,)
rep(j,,S.node) bz[j][i]=bz[bz[j][i-]][i-];
ll ans=; now=;
int cnt3=;
rep(i,,len-)
{
if (s[i]=='-')
{
int x=,y=;
ans-=dis[now];
it=M.find(dfn[now]); it++;
if (it!=M.end()) x=rl[*it]; it--;
if (it!=M.begin()) y=rl[*--it];
M.erase(dfn[now]);
if (x) ans+=dis[lca(now,x)];
if (y) ans+=dis[lca(now,y)];
if (x&&y) ans-=dis[lca(x,y)];
now=zt[--cnt3];
} else
{
int x=,y=;
now=S.ch[now][s[i]-'a'];
zt[++cnt3]=now;
ans+=dis[now];
it=M.insert(dfn[now]).first;
it++;
if (it!=M.end()) x=rl[*it]; it--;
if (it!=M.begin())
{
y=rl[*--it];
}
if (x) ans-=dis[lca(now,x)];
if (y) ans-=dis[lca(now,y)];
if (x&&y) ans+=dis[lca(x,y)];
// cout<<lca(pos[now],x)<<" "<<lca(pos[now],y)<<" "<<x<<" "<<y<<endl;
}
printf("%lld\n",ans);
}
return ;
}

最新文章

  1. MySQL高级知识- MySQL的架构介绍
  2. Yii2:避免文件路径暴漏,代理访问文件
  3. TinyFrame升级之七:重构Repository和Unit Of Work
  4. React Native 的高度与宽度设置
  5. SoapUI中如何传递cookie
  6. SQL Server 2008 Data Types and Entity Framework 4
  7. 宏定义中使用do{}while(0)的好处 (转载)
  8. 【转】 Android用于提示等待的ProgressDialog
  9. shiro 介绍和基本使用
  10. jcp 打印机字体变淡变模糊bootstrap
  11. Python学习笔记–Chapter 2
  12. Postman 设置全局变量和环境变量设置(之 图形界面设置变量)
  13. Javascript高级编程学习笔记(51)—— DOM2和DOM3(3)操作样式表
  14. QT 设置应用程序名称和主窗口标题
  15. Struts2 环境搭建
  16. bootStrap中的ul导航3-垂直导航
  17. Android中asset文件夹和raw文件夹区别(转载)
  18. 函数参数 f_arg, *args, **kwargs
  19. (转)MapReduce Design Patterns(chapter 7 (part 1))(十三)
  20. LIS和LCS LCIS

热门文章

  1. python3+selenium入门05-元素操作及常用方法
  2. 设计模式C++学习笔记之二十(完结篇 &amp; 面向对象原则)设计模式C++实例下载
  3. 理解和使用ThreadLocal类
  4. 激活函数Sigmoid、Tanh、ReLu、softplus、softmax
  5. centos如何安装Python3
  6. java中package指什么
  7. Linux i2c 读写程序
  8. 运输层TCP/UDP
  9. [javascript]XMLHttpRequest GET/SET HTTP头与改变HTTP METHOD示例代码
  10. UpdatePanel1里面使用FileUpload控件