题解 P6292 【【模板】区间本质不同子串个数】
Fuyuki
2020-04-05 18:23:11
对于每个本质不同的字符串 $T$，假设在前缀 $[1,r]$ 中最后一次出现的位置（右端点）为 $last_T$，那么当左端点取到 $[1,last_T-|T|+1]$ 这个区间内的时候，$T$ 会对答案产生 $1$ 的贡献。
采用扫描线的思路，对每个右端点维护所有左端点的答案。
如果把反串的后缀树建出来，那么将右端点右移一位到达 $r$ 就相当于将后缀树上一条到根的路径上的所有字符串的 $last$ 修改成 $r$。如果把这个看作 LCT 中的 access 操作，可以发现划分出来的每条链上的 $last$ 都相同，并且代表的字符串长度连续。
因此直接用 LCT 进行修改，将链合并的时候就是将一段长度连续的本质不同字符串的 $last$ 进行修改，这个对答案的影响可以表现成区间加一个公差为 $1$ 的等差数列，用线段树维护即可。
注意到 access 操作的次数是均摊 $O(logn)$，那么只会进行 $O(nlogn)$ 次线段树上的区间修改，复杂度是 $O(nlog^2n)$ 的。而线段树上查询一次的复杂度是 $O(logn)$，所以总复杂度是 $O(nlog^2n+mlogn)$。
我的实现中将区间加等差数列单点查询转化成区间加常数区间查询，用树状数组实现的时候感觉稍微好写一些。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define P pair<int,int>
#define ll long long int
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=2e5+1,INF=0x3f3f3f3f;
V cmin(int&x,int y){if(y-x>>31)x=y;}
namespace SAM{
int ch[N][26],fa[N],len[N],tot=1,last=1;
V cpy(int x,int y){FOR(i,0,25)ch[x][i]=ch[y][i];}
I ins(int x){
int p(last),np,q,nq;
len[np=last=++tot]=len[p]+1;
while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
if(!p)return fa[np]=1,last;
if(len[q=ch[p][x]]==len[p]+1)return fa[np]=q,last;
cpy(nq=++tot,q),len[nq]=len[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq;
while(p&&ch[p][x]==q)ch[p][x]=nq,p=fa[p];
return last;
}
}
namespace seg{
ll c[N],d[N];
I lowbit(int x){return x&-x;}
V add(int x,int y){for(ll w=x*y;x<N;x+=lowbit(x))c[x]+=y,d[x]+=w;}
ll ask(int x){
ll out=0,tmp=0;
for(int p=x;p;p^=lowbit(p))out+=c[p],tmp+=d[p];
return out*(x+1)-tmp;
}
ll ask(int l,int r){return ask(r)-ask(l-1);}
V add(int l,int r,int x){add(l,x),add(r+1,-x);}
}
namespace LCT{
int fa[N],ch[N][2],last[N],tag[N],len[N],val[N];
I id(int x){return x==ch[fa[x]][1];}
I nrt(int x){return x==ch[fa[x]][id(x)];}
V upd(int x){val[x]=len[x];FOR(i,0,1)cmin(val[x],val[ch[x][i]]);}
V rot(int x){
int y=fa[x],z=fa[y],p=id(x),w=ch[x][p^1];
if(nrt(y))ch[z][id(y)]=x;if(w)fa[w]=y;
fa[y]=x,fa[x]=z,ch[x][p^1]=y,ch[y][p]=w,upd(y),upd(x);
}
V add(int x,int w){last[x]=tag[x]=w;}
V psd(int x){if(tag[x])FOR(i,0,1)add(ch[x][i],tag[x]);tag[x]=0;}
V psa(int x){if(nrt(x))psa(fa[x]);psd(x);}
V spl(int x){
for(psa(x);nrt(x);rot(x))if(nrt(fa[x]))
rot(id(x)==id(fa[x])?fa[x]:x);
}
V acc(int x,int now){
for(int p=x,y=0;p;p=fa[y=p]){
spl(p),ch[p][1]=y,upd(p);
if(last[p])seg::add(last[p]-SAM::len[p]+1,last[p]-val[p]+1,-1);
}
spl(x),add(x,now),seg::add(now-SAM::len[x]+1,now,1);
}
V init(){
val[0]=INF;
FOR(i,1,SAM::tot){
val[i]=len[i]=SAM::len[fa[i]=SAM::fa[i]]+1;
tag[i]=ch[i][0]=ch[i][1]=last[i]=0;
}
}
}
char a[N];
ll ans[N];
vector<P>q[N];
int T,n,m,l,r,pos[N];
int main(){
scanf("%s%d",a+1,&m),n=strlen(a+1);
FOR(i,1,m)scanf("%d%d",&l,&r),q[r].push_back(P(i,l));
FOR(i,1,n)pos[i]=SAM::ins(a[i]-'a');
LCT::init();
FOR(i,1,n){
LCT::acc(pos[i],i);
for(P x:q[i])ans[x.first]=seg::ask(x.second,i);
}
FOR(i,1,m)cout<<ans[i]<<'\n';
return 0;
}
```