题目描述
给定一个字符串 \(S\) ，\(m\) 次询问，每次询问 \(S_{[l,r]}\) 中有多少个本质不同的子串。
\(1 \leq |S| \leq 10^5,1 \leq m \leq 2 \times 10^5\) 。
算法描述
考虑 HH的项链 那道题，扫描右端点，维护对于某些串，能贡献的最大的左端点。
假设有一个长为 \(len\) 的串，最后一次是在 \(x\) 出现，容易发现此时右端点已经扫过 \(x\) ，所以左端点在 \([1,x - len + 1]\) 就可以贡献一个。
考虑建出 \(S\) 的 SAM，每次跳到前缀 \([1,r]\) 相应的节点 \(x\) ，考虑从节点 \(x\) 到根的整条路径的 \(lst\) 都应该改成 \(r\) 。这种拉通染色很像 LCT 的 access 操作。用 LCT 维护这个东西，每次以一个 splay 为单位向上跳，由于现在节点为当前实链最底端的点，可以知道这条实链代表的最长长度 \(lmax\) ，splay 后取父亲可以得到这条实链最短长度 \(lmin = len_{fa} + 1\)。
相当于减去 \([lmin,lmax]\) 长度先前出现的贡献，由于是到根，所以对于 \([1,r]\) 长度都加上在 \(r\) 出现的贡献。
仔细研究贡献，假设 \([x,y]\) 长度在 \(z\) 最后一次出现，相当于对于 \(l \in [z - y + 1,z - x + 1]\) ，\(l\) 每增加一个，本质不同的串就多一个。
对于 \(l \in [1,z - y]\) ，贡献都不变。
神秘地，由于右端点一直在向右单调增，我们可以在线段树上将 \([z - y + 1,z - x + 1]\) 区间 \(+1\) ，查询查 \([l,r]\) 区间和即可。手摸各种情况发现这样是对的！
这其实是将等差数列加、单点查变成了区间加、区间查。
一开始全部设成虚边，然后 LCT 维护即可。
时间复杂度 \(\Theta(n \log^2 n + q\log n)\) ，细节详见代码。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
char s[N];
int n,m;
typedef long long ll;
ll ans[N];
struct Q{
int l,r,id;
}q[N];
struct Segment_Tree{
ll tag[N << 2],a[N << 2];
inline void pushdown(int pos,int l,int r)
{
int mid = (l + r) >> 1;
a[pos << 1] += (mid - l + 1) * tag[pos]; tag[pos << 1] += tag[pos];
a[pos << 1 | 1] += (r - mid) * tag[pos]; tag[pos << 1 | 1] += tag[pos];
tag[pos] = 0;
}
inline void pushup(int pos) {a[pos] = a[pos << 1] + a[pos << 1 | 1];}
inline void modify(int l,int r,int L,int R,ll k,int pos)
{
if(L <= l && r <= R) {a[pos] += k * (r - l + 1); tag[pos] += k; return;}
int mid = (l + r) >> 1;
pushdown(pos,l,r);
if(L <= mid) modify(l,mid,L,R,k,pos << 1);
if(R > mid) modify(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
inline ll query(int l,int r,int L,int R,int pos)
{
if(L <= l && r <= R) return a[pos];
pushdown(pos,l,r);
int mid = (l + r) >> 1; ll ret = 0;
if(L <= mid) ret += query(l,mid,L,R,pos << 1);
if(R > mid) ret += query(mid + 1,r,L,R,pos << 1 | 1);
pushup(pos);
return ret;
}
}sgt;
struct SAM{
struct Node{
int son[26],link,len;
}a[N];
int lst = 1,tot = 1;
inline void ist(char c)
{
int cur = ++tot; a[cur].len = a[lst].len + 1;
int p = lst,q;
lst = cur;
while(p && !a[p].son[c - 'a']) a[p].son[c - 'a'] = cur,p = a[p].link;
if(!p) {a[cur].link = 1; return;}
q = a[p].son[c - 'a'];
if(a[q].len == a[p].len + 1) {a[cur].link = q; return;}
int np = ++tot;
memcpy(a[np].son,a[q].son,sizeof(a[q].son));
a[np].len = a[p].len + 1;
a[np].link = a[q].link;
while(p && a[p].son[c - 'a'] == q) a[p].son[c - 'a'] = np,p = a[p].link;
a[q].link = np; a[cur].link = np;
}
}sam;
struct LCT{
struct Node{
int son[2],fa,val,tag;
}a[N];
inline void change(int x,int v) {a[x].val = v; a[x].tag = v;}
inline void pushdown(int x) {if(!a[x].tag) return; if(a[x].son[0]) change(a[x].son[0],a[x].tag); if(a[x].son[1]) change(a[x].son[1],a[x].tag); a[x].tag = 0;}
inline int which(int x) {return (x == a[a[x].fa].son[1]);}
inline bool isroot(int x) {return (x != a[a[x].fa].son[0] && x != a[a[x].fa].son[1]);}
inline void rorate(int x)
{
int y = a[x].fa,z = a[y].fa,dir = which(x);
a[y].son[dir] = a[x].son[dir ^ 1];
if(a[x].son[dir ^ 1]) a[a[x].son[dir ^ 1]].fa = y;
a[x].fa = z;
if(!isroot(y)) a[z].son[which(y)] = x;
a[y].fa = x;
a[x].son[dir ^ 1] = y;
}
inline void splay(int x)
{
static int st[N],top = 0; top = 0;
int tmp = x;
while(tmp) st[++top] = tmp,tmp = a[tmp].fa;
while(top) pushdown(st[top]),top--;
while(!isroot(x))
{
if(!isroot(a[x].fa))
rorate((which(x) ^ which(a[x].fa)) ? x : a[x].fa);
rorate(x);
}
}
inline void access(int x,int nv)
{
for(int rc = 0;x;rc = x,x = a[x].fa)
{
splay(x);
a[x].son[1] = rc;
if(a[x].val) sgt.modify(1,n,a[x].val - sam.a[x].len + 1,a[x].val - sam.a[a[x].fa].len,-1,1);
change(x,nv);
}
sgt.modify(1,n,1,nv,1,1);
}
}lct;
int main()
{
scanf("%s",s + 1);
n = strlen(s + 1);
for(int i = 1;i <= n;i++) sam.ist(s[i]);
scanf("%d",&m);
for(int i = 1;i <= m;i++)
scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
for(int i = 2;i <= sam.tot;i++) lct.a[i].fa = sam.a[i].link;
sort(q + 1,q + m + 1,[&](Q x,Q y) {return x.r < y.r;});
for(int i = 1,j = 1,np = 1;i <= n;i++)
{
np = sam.a[np].son[s[i] - 'a'];
lct.access(np,i);
while(j <= m && q[j].r == i) ans[q[j].id] = sgt.query(1,n,q[j].l,q[j].r,1),j++;
}
for(int i = 1;i <= m;i++) printf("%lld\n",ans[i]);
return 0;
}