题目
可能是一个乱搞做法，同时也跪求有人能帮我分析一下复杂度
还是先来看比较简单的\(68pts\)，也就是\(l=1,r=|S|\)的情况
我们可以直接把\(S\)串和所有的\(T\)串一起建一个广义\(SAM\)，用一个\(vector\)维护每个\(T\)加入\(SAM\)时新产生的节点
我们只需要求出来这些新增节点没有在\(S\)串出现的本质不同的子串个数就好了
我们提前处理好每一个节点的\(endpos\)，标记一下其是否在\(S\)中出现过
对于那些新出现在\(SAM\)上的节点\(x\)我们可以直接判断一下其是否在\(S\)中出现过，经典操作自然是\(ans+=len[x]-len[fa[x]]\)
但是考虑到\(x\)在\(parent\)树上的祖先自然也在当前的\(T\)中出现过，于是我们还需要考虑这些节点的贡献
倍增？看起来好像非常可行，但是还有一个问题，就是判重
显然在处理一个\(T\)的时候\(parent\)树上的一个节点不能被计算两次，于是在\(parent\)树上倍增又不太可行了，因为不太方便我们打标记来判重
倍增不行我们就暴力啊，我们直接暴力访问\(x\)的祖先们，一旦有一个祖先在之前被访问过或者是在\(S\)中出现过，那么我们就不在往上跳了
至于复杂度我也不知道是什么，我甚至都觉得这个样子最坏会导致每次都把\(parent\)树遍历一遍，所以求有神仙能帮忙分析一下这个玄学的复杂度
\(68pts\)代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define maxn 3000005
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
char S[maxn],T[maxn];
int n,m,l,r,cnt=1,lst=1,num;
struct E{int v,nxt;}e[maxn];
std::vector<int> v[100005];
int fa[maxn],len[maxn],endpos[maxn],son[maxn][26],head[maxn],vis[maxn];
int top,st[maxn];
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
inline void ins(int c,int o)
{
int p=++cnt,f=lst; lst=p;
len[p]=len[f]+1,endpos[p]=o;
if(o>1) v[o-1].push_back(p);
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
int x=son[f][c];
if(len[f]+1==len[x]) {fa[p]=x;return;}
int y=++cnt;
if(o>1) v[o-1].push_back(y);
len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;
for(re int i=0;i<26;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
void dfs(int x) {if(endpos[x]!=1) endpos[x]=0; for(re int i=head[x];i;i=e[i].nxt) dfs(e[i].v),endpos[x]|=endpos[e[i].v];}
int main()
{
scanf("%s",S+1);n=strlen(S+1);
for(re int i=1;i<=n;i++) ins(S[i]-'a',1);
scanf("%d",&m);
for(re int i=1;i<=m;i++)
{
scanf("%s",T+1),n=strlen(T+1);
scanf("%d%d",&l,&r);
lst=1;
for(re int j=1;j<=n;j++)
ins(T[j]-'a',i+1);
}
for(re int i=2;i<=cnt;i++) add(fa[i],i); dfs(1);
for(re int i=1;i<=m;i++)
{
LL ans=0;top=0;
for(re int j=0;j<v[i].size();j++)
{
int t=v[i][j];
if(endpos[t]||vis[t]) continue;
ans+=len[t];st[++top]=t;vis[t]=1;
while(!vis[fa[t]]&&fa[t]&&!endpos[fa[t]]) t=fa[t],vis[t]=1,st[++top]=t;
ans-=len[fa[t]];
}
for(re int j=1;j<=top;j++) vis[st[j]]=0;
printf("%lld\n",ans);
}
return 0;
}再来看看剩下的非特殊情况
看到\(S\)串里的区间我们就知道我们不能只是粗略维护\(endpos\)集合了，我们有时候甚至得关心\(endpos\)里到底有哪些元素
于是我们得用一个可持久化数据结构来维护一下\(endpos\)集合
这里选择的是主席树，至于做法和上面差不多
我们还是对\(SAM\)上新增的节点以及其祖先算贡献，每次用主席树找出当前节点\(x\)的\(endpos\)集合里小于等于\(r\)的最大值\(now\)
根据\(now\)和\(l\)的关系进行讨论
如果\(now-len[fa[x]]>=l\)，那么就说明当前这个节点表示的子串里已经有一些完全出现在了\([l,r]\)中，所以我们没有必要往上进行了，在这里计算贡献就好了，减掉那些完全出现在\([l,r]\)里的子串，也就是\(now-l+1\)，但是可能这个节点根本产生不了这些子串，于是需要和\(len[x]\)取一个\(min\)
否则的话这个节点表示的子串里没有一个完全出现在\([l,r]\)中，所以还要继续算下去
但是这样每次都需要在主席树里二分，可以加一个小优化，一旦\(endpos\)集合的最大值小于\(l\)，或者最小值大于\(r\)，我们就不在主席树里二分了
这里的复杂度和上面相比多了一个\(log\)，于是更加玄学了，并不保证代码能随时不T
交上去能获得取决于评测机稳定程度的分数的代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define maxn 3000005
#define M 10000005
#define re register
#define LL long long
inline int min(int a,int b) {return (a<b)?a:b;}
inline int max(int a,int b) {return (a>b)?a:b;}
char S[500005],T[500005];
int n,m,cnt=1,lst=1,num,U,__,tot;
struct E{int v,nxt;}e[maxn];
std::vector<int> a[100005];
int x[100005],y[100005];
int fa[maxn],len[maxn],endpos[maxn],son[maxn][26],head[maxn];
int rt[maxn],sz[maxn],to[maxn],_to[maxn],mx[maxn],tx[maxn];
unsigned short vis[maxn];
int top,st[500005];
int l[M],r[M],d[M];
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
inline void ins(int c,int pos,int o)
{
int p=++cnt,f=lst; lst=p;
len[p]=len[f]+1,endpos[p]=tx[p]=mx[p]=pos;
if(o) a[o].push_back(p);
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
int x=son[f][c];
if(len[f]+1==len[x]) {fa[p]=x;return;}
int y=++cnt;
len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;
for(re int i=0;i<26;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
void dfs(int x)
{
to[x]=++__;_to[__]=x;sz[x]=1;
if(!tx[x]) tx[x]=U+1;
for(re int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;
dfs(v),sz[x]+=sz[v];
mx[x]=max(mx[v],mx[x]);
tx[x]=min(tx[x],tx[v]);
}
}
int change(int pre,int x,int y,int pos)
{
int root=++tot;
d[root]=d[pre]+1;
if(x==y) return root;
l[root]=l[pre],r[root]=r[pre];
int mid=x+y>>1;
if(pos<=mid) l[root]=change(l[pre],x,mid,pos);
else r[root]=change(r[pre],mid+1,y,pos);
return root;
}
int query(int p1,int p2,int x,int y,int pos)
{
if(x==y) return d[p2]-d[p1];
int mid=x+y>>1;
if(pos<=mid) return query(l[p1],l[p2],x,mid,pos);
return d[l[p2]]-d[l[p1]]+query(r[p1],r[p2],mid+1,y,pos);
}
int ask(int p1,int p2,int x,int y,int k)
{
if(x==y) return x;
int now=d[l[p2]]-d[l[p1]];
int mid=x+y>>1;
if(k>now) return ask(r[p1],r[p2],mid+1,y,k-now);
return ask(l[p1],l[p2],x,mid,k);
}
inline int find(int X,int o)
{
if(y[o]<tx[X]||x[o]>mx[X]) return -1;
int Y=to[X]+sz[X]-1;
X=to[X];
int T=query(rt[X-1],rt[Y],1,U,y[o]);
if(!T) return -1;return ask(rt[X-1],rt[Y],1,U,T);
}
int main()
{
scanf("%s",S+1);n=strlen(S+1);U=n;
for(re int i=1;i<=n;i++) ins(S[i]-'a',i,0);
scanf("%d",&m);
for(re int i=1;i<=m;i++)
{
scanf("%s",T+1),n=strlen(T+1);
scanf("%d%d",&x[i],&y[i]);lst=1;
for(re int j=1;j<=n;j++) ins(T[j]-'a',0,i);
}
for(re int i=2;i<=cnt;i++) add(fa[i],i); dfs(1);
for(re int i=1;i<=cnt;i++)
if(endpos[_to[i]]) rt[i]=change(rt[i-1],1,U,endpos[_to[i]]);else rt[i]=rt[i-1];
for(re int i=1;i<=m;i++)
{
LL ans=0;top=0;int now=0;
for(re int j=0;j<a[i].size();j++)
{
int t=a[i][j];
if(vis[t]) continue;
vis[t]=1,st[++top]=t;ans+=len[t];
now=find(t,i);
if(now!=-1&&now-len[fa[t]]>=x[i])
{ans-=min(len[t],now-x[i]+1);continue;}
while(1)
{
if(vis[fa[t]]||!fa[t]) {ans-=len[fa[t]];break;}
t=fa[t],vis[t]=1,st[++top]=t;
now=find(t,i);
if(now!=-1&&now-len[fa[t]]>=x[i]) {ans-=min(now-x[i]+1,len[t]);break;}
}
}
for(re int j=1;j<=top;j++) vis[st[j]]=0;
printf("%lld\n",ans);
}
return 0;
}