LCT 好题。
description
给定一个长度为 \(n\) 的只包含小写英文字母的字符串。
有 \(m\) 次询问，每次问一个子串的本质不同子串个数。
-
\(n\leq 10^5\)
-
\(m\leq 2\times 10^5\)
solution
考虑按询问右端点从小到大离线。
先建出母串的 SAM，设 \(\text{len}_x\) 表示状态 \(x\) 代表的等价类中最长的子串的长度，\(\text{rpos}_x\) 表示 \(\max\limits_{r_i\in \text{endpos}(x)}\{r_i\}\)。
我们让所有子串只在它最后一次出现的位置贡献，那么可以这样算母串的本质不同子串个数：
-
对于每个 SAM 状态，对 \([\text{rpos}_x-\text{len}_x+1,\text{rpos}_x-\text{len}_{fa_x}]\) 做区间加。
-
统计 \(i\in [1,n]\) 每个位置的和。
可以发现，这样做能让 \([l,n]\) 的和表示左端点在 \(l\) 及其右边的本质不同子串的数量。
所以我们只需要在右指针右移过程中维护每个位置的和就行了。
观察到 \(\text{len}\) 不会随着右指针的右移发生改变，所以我们只需要考虑 \(\text{rpos}\) 的变化。
考虑母串的 parent 树，右指针从 \(i-1\) 右移到 \(i\) 就相当于从前缀 \([1,i]\) 所在的状态开始往上跳，把它和它所有祖先的 \(\text{rpos}\) 改成 \(i\)（因为 \(i\) 一定是当前所有 \(\text{endpos}\) 集合中最大的元素）。
因为这条链上的每个点的 \(\text{rpos}\) 并非完全一样，所以不好直接维护。
但是注意到这是个类似染色的过程，能让我们联想到 LCT 的 access 操作，每条实链上节点的 \(\text{rpos}\) 都相同。
于是直接用 LCT 维护每条实链的 \(\text{rpos}\)，在 access 的过程中进行区间加减操作即可。维护区间加区间和可以用线段树实现。
询问的话只需要在线段树上询问 \([l,r]\) 的区间和。
时间复杂度 \(O(n\log^2 n+m\log n)\)。
code
#include<bits/stdc++.h>
using namespace std;
using E=long long;
struct segment{
vector<E> sum,tag,len;
void build(int u,int l,int r){
len[u]=r-l+1;
if(l==r) return ;
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
segment(int sz=0){
sum=tag=len=vector<E>(sz*4+10);
if(!sz) return ;
build(1,1,sz);
}
void spread(int u,int val){
if(!u) return ;
sum[u]+=val*1ll*len[u];
tag[u]+=val;
}
void dn(int u){
if(!tag[u]) return ;
spread(u<<1,tag[u]),spread(u<<1|1,tag[u]);
tag[u]=0;
}
void add(int u,int l,int r,int L,int R,int val){
if(L<=l&&r<=R){
spread(u,val);
return ;
}
dn(u);
int mid=(l+r)>>1;
if(L<=mid) add(u<<1,l,mid,L,R,val);
if(mid<R) add(u<<1|1,mid+1,r,L,R,val);
sum[u]=sum[u<<1]+sum[u<<1|1];
}
E query(int u,int l,int r,int L,int R){
if(L<=l&&r<=R) return sum[u];
dn(u);
E ret=0;
int mid=(l+r)>>1;
if(L<=mid) ret=query(u<<1,l,mid,L,R);
if(mid<R) ret+=query(u<<1|1,mid+1,r,L,R);
return ret;
}
};
struct linkCutTree{
struct node{
int son[2],par;
int val,tag,w;
};
vector<node> tr;
segment T;
int n;
linkCutTree(int sz=0){
tr=vector<node>(sz+1);
T=segment(sz);
n=sz;
}
#define ls(u) tr[(u)].son[0]
#define rs(u) tr[(u)].son[1]
#define par(u) tr[(u)].par
#define val(u) tr[(u)].val
#define w(u) tr[(u)].w
#define tag(u) tr[(u)].tag
void spread(int u,int val){ if(!u) return ; w(u)=val,tag(u)=val; }
void dn(int u){ if(!tag(u)) return ; spread(ls(u),tag(u)),spread(rs(u),tag(u)),tag(u)=0; }
int nroot(int u){ return u==ls(par(u))||u==rs(par(u)); }
int get(int u){ return u==rs(par(u)); }
void rotate(int u){
int p=par(u),j=par(p),op=get(u);
if(nroot(p)) tr[j].son[get(p)]=u;
if(tr[u].son[op^1]) par(tr[u].son[op^1])=p;
tr[p].son[op]=tr[u].son[op^1];
tr[u].son[op^1]=p;
par(p)=u;
par(u)=j;
}
void update(int u){
if(nroot(u)) update(par(u));
dn(u);
}
void splay(int u){
update(u);
while(nroot(u)){
int f=par(u);
if(nroot(f)){
if(get(u)==get(f)) rotate(f);
else rotate(u);
}
rotate(u);
}
}
int top(int u){
splay(u);
dn(u);
while(ls(u)) u=ls(u),dn(u);
return splay(u),u;
}
void access(int u,int now){
int p=0;
while(u){
int t=top(u);
if(w(u)&&val(u)) T.add(1,1,n,w(u)-val(u)+1,w(u)-val(par(t)),-1);
if(val(u)) T.add(1,1,n,now-val(u)+1,now-val(par(t)),1);
splay(u);
w(u)=now;
if(ls(u)) spread(ls(u),now);
rs(u)=p;
p=u;
u=par(u);
}
}
void reset(int u,int p,int v){
val(u)=v,par(u)=p;
w(u)=0;
}
E query(int l,int r){
assert(l<=r);
return T.query(1,1,n,l,r);
}
#undef ls
#undef rs
#undef par
#undef val
#undef w
#undef tag
};
struct SAM{
vector<array<int,26>> ch;
vector<int> fa,len;
int idx,lst;
linkCutTree T;
SAM(int sz){
idx=1;
lst=1;
ch=vector<array<int,26>>(sz*2);
fa=len=vector<int>(sz*2);
}
inline int f(char c){ return (int)(c-'a'); }
int extend(char c){
idx++;
int p=lst;
len[idx]=len[lst]+1;
while(p&&ch[p][f(c)]==0){
ch[p][f(c)]=idx;
p=fa[p];
}
if(!p){
fa[idx]=1;
return lst=idx,idx;
}
int q=ch[p][f(c)];
if(len[q]==len[p]+1){
fa[idx]=q;
return lst=idx,idx;
}
int np=idx;
idx++;
ch[idx]=ch[q]; len[idx]=len[p]+1; fa[idx]=fa[q];
while(p&&ch[p][f(c)]==q){
ch[p][f(c)]=idx;
p=fa[p];
}
fa[q]=idx,fa[np]=idx;
lst=np;
return np;
}
void build(){
T=linkCutTree(idx);
for(int i=1; i<=idx; i++){
//cerr<<i<<' '<<fa[i]<<' '<<len[i]<<endl;
T.reset(i,fa[i],len[i]);
}
}
};
int main(){
#ifdef zzafanti
freopen("in.in","r",stdin);
#endif // zzafanti
cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);
string str;
int n,m;
cin>>str;
n=str.size();
str=" "+str;
cin>>m;
vector<vector<pair<int,int>>> Q(n+1);
for(int i=1; i<=m; i++){
int l,r;
cin>>l>>r;
Q[r].emplace_back(make_pair(i,l));
}
SAM sam(n);
vector<int> pos(n+1);
for(int i=1; i<=n; i++){
pos[i]=sam.extend(str[i]);
}
sam.build();
vector<E> ans(m+1);
for(int i=1; i<=n; i++){
sam.T.access(pos[i],i);
for(auto pt:Q[i]){
int idx=pt.first,l=pt.second;
ans[idx]=sam.T.query(l,i);
}
}
for(int i=1; i<=m; i++){
cout<<ans[i]<<'\n';
}
return 0;
}