Description
给定一个长度为 (n) 的字符串 (S)，有 (m) 个询问，每次询问给定 (l,r)，求 (S[l..r]) 中有多少个本质不同的子串。
Solution
考虑离线，将所有询问挂在右端点上，从左到右扫描整个序列，设当前扫描到的位置为 (r)
用线段树统计答案，第 (i) 位表示 (S[1..r]) 中最后一次出现时左端点为 (i) 的子串数目，于是询问就是求 ([l,r]) 的和
考虑修改，当新增字符 (S[r]) 时会对 ([1,r]) 各产生 (1) 的贡献，需要去重
用 SAM 维护串，则从 (S[1..r]) 对应节点 (p_0) 沿着后缀链接跳，经过的所有结点上一次出现的右端点 (lastpos) 便能计算出需要在线段树上 (-1) 的区间 ([lastpos[p]-len[p]+1,lastpos[p]-len[fa[p]]])，跳完后还要把这些节点的 (lastpos) 都设置为 (p)
这样做非常慢，考虑到 (lastpos) 相同的点可以放在一起处理，每次从 (p_0) 跳到根的过程相当于把这条链并起来的过程，不难想到用 LCT 的 Access 操作来维护
每次处理相当于将根到 (p_0) 的路径 Access 一下，在 Access 的过程中顺便统计答案并修改 (lastpos)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int n,m;
struct segseg
{
int val[N],tag[N];
void put(int p,int l,int r,int v)
{
tag[p]+=v;
val[p]+=(r-l+1)*v;
}
void pushup(int p)
{
val[p]=val[p*2]+val[p*2+1];
}
void pushdown(int p,int l,int r)
{
if(tag[p])
{
put(p*2,l,(l+r)/2,tag[p]);
put(p*2+1,(l+r)/2+1,r,tag[p]);
tag[p]=0;
}
}
void modify(int p,int l,int r,int ql,int qr,int v)
{
if(l>qr || r<ql) return;
if(l>=ql&&r<=qr)
{
put(p,l,r,v);
}
else
{
pushdown(p,l,r);
modify(p*2,l,(l+r)/2,ql,qr,v);
modify(p*2+1,(l+r)/2+1,r,ql,qr,v);
pushup(p);
}
}
int query(int p,int l,int r,int ql,int qr)
{
if(l>qr || r<ql) return 0;
if(l>=ql&&r<=qr) return val[p];
pushdown(p,l,r);
return query(p*2,l,(l+r)/2,ql,qr) + query(p*2+1,(l+r)/2+1,r,ql,qr);
}
} seg;
struct SAM
{
int len[N], ch[N][26], fa[N], ind, last;
int t[N], a[N], cnt[N], f[N];
SAM()
{
ind = last = 1;
}
void extend(int id)
{
int cur = (++ ind), p;
len[cur] = len[last] + 1;
cnt[cur] = 1;
for (p = last; p && !ch[p][id]; p = fa[p]) ch[p][id] = cur;
if (!p) fa[cur] = 1;
else
{
int q = ch[p][id];
if (len[q] == len[p] + 1) fa[cur] = q;
else
{
int tmp = (++ ind);
len[tmp] = len[p] + 1;
for(int i=0; i<26; i++) ch[tmp][i] = ch[q][i];
fa[tmp] = fa[q];
for (; p && ch[p][id] == q; p = fa[p]) ch[p][id] = tmp;
fa[cur] = fa[q] = tmp;
}
}
last = cur;
}
} sam;
struct lctlct
{
int top, q[N], ch[N][2], fa[N], rev[N];
int a[N], tag[N], siz[N], val[N];
inline void pushup(int x)
{
}
void put(int p,int v)
{
if(!p) return;
tag[p]=val[p]=v;
}
inline void pushdown(int x)
{
if(rev[x])
{
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]^=1;
swap(ch[x][0],ch[x][1]);
}
if(tag[x])
{
put(ch[x][0],tag[x]);
put(ch[x][1],tag[x]);
tag[x]=0;
}
}
inline bool isroot(int x)
{
return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
}
inline void rotate(int p)
{
int q=fa[p], y=fa[q], x=ch[fa[p]][1]==p;
ch[q][x]=ch[p][x^1];
fa[ch[q][x]]=q;
ch[p][x^1]=q;
fa[q]=p;
fa[p]=y;
if(y) if(ch[y][0]==q) ch[y][0]=p;
else if(ch[y][1]==q) ch[y][1]=p;
pushup(q);
pushup(p);
}
inline void splay(int x)
{
q[top=1]=x;
for(int i=x; !isroot(i); i=fa[i]) q[++top]=fa[i];
for(int i=top; i; i--) pushdown(q[i]);
for(; !isroot(x); rotate(x))
if(!isroot(fa[x]))
rotate((ch[fa[x]][0]==x)==(ch[fa[fa[x]]][0]==fa[x])?fa[x]:x);
}
void access(int x,int k)
{
int y=0;
for(;x;y=x,x=fa[x])
{
splay(x);
if(val[x])
{
//cout<<val[x]-sam.len[x]+1<<" "<<val[x]-sam.len[fa[x]]<<endl;
seg.modify(1,1,n,val[x]-sam.len[x]+1,val[x]-sam.len[fa[x]],-1);
}
ch[x][1]=y;
}
put(y,k);
seg.modify(1,1,n,1,k,1);
}
} lct;
struct request
{
int id,l;
};
vector <request> req[N];
char s[N];
int ans[N],pos[N];
signed main()
{
ios::sync_with_stdio(false);
cin>>(s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
{
sam.extend(s[i]-'a');
pos[i]=sam.last;
}
for(int i=2;i<=sam.ind;i++)
{
lct.fa[i]=sam.fa[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
req[r].push_back({i,l});
}
for(int i=1;i<=n;i++)
{
lct.access(pos[i],i);
for(request q:req[i])
{
ans[q.id]=seg.query(1,1,n,q.l,i);
}
}
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<endl;
}
}