SA解法

#include<bits/stdc++.h>
#define lc(p) ((p)<<1)
#define rc(p) ((p)<<1|1)
using namespace std;
typedef long long ll;
const int mxn=2.5e6+500,inf=1e9;
int n,m,p,sa[mxn],rk[mxn],oldrk[mxn],cnt[mxn],id[mxn],height[mxn],lg2[mxn],sid[mxn],len[mxn];
struct N{
	int mx,la;
}tr[3000010];
void pushup(int p){
	tr[p].mx=max(tr[lc(p)].mx,tr[rc(p)].mx);
} 
void pd(int p,int v){
	tr[p].mx=min(tr[p].mx,v);
	tr[p].la=min(tr[p].la,v);
}
void pushdown(int p){
	if(tr[p].la<inf){
		pd(lc(p),tr[p].la);
		pd(rc(p),tr[p].la);
		tr[p].la=inf;
	}
}
void bt(int p,int l,int r){
	tr[p]={0,inf};
	if(l==r)return ;
	int mid=(l+r)>>1;
	bt(lc(p),l,mid);
	bt(rc(p),mid+1,r);
}
void change(int p,int l,int r,int x,int v){
	if(l==r){
		tr[p].mx=max(tr[p].mx,v);
		return ;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(p),l,mid,x,v);
	else change(rc(p),mid+1,r,x,v);
	pushup(p);
}
int getans(int p,int l,int r,int x,int y){
	if(l==r)return min(tr[p].mx,y-r+1);
	pushdown(p);
	int mid=(l+r)>>1;
	if(tr[lc(p)].mx>=y-mid+1)return getans(lc(p),l,mid,x,y);
	else return max(tr[lc(p)].mx,getans(rc(p),mid+1,r,x,y));
}
int find(int p,int l,int r,int x,int y,bool &fl){
	if(l>y||r<x)return 0;
	if(l>=x&&r<=y){
		if(tr[p].mx>=y-r+1){
			fl=1;
			return getans(p,l,r,x,y);
		}
		return tr[p].mx;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x>mid)return find(rc(p),mid+1,r,x,y,fl);
	int ans=find(lc(p),l,mid,x,y,fl);
	if(fl||y<=mid)return ans;
	return max(ans,find(rc(p),mid+1,r,x,y,fl));
}
int findp(int p,int l,int r,int x){
	if(l==r)return tr[p].mx;
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid)return findp(lc(p),l,mid,x);
	else return findp(rc(p),mid+1,r,x);
}
int ql[100010],qr[100010];
int ss[mxn];
ll ans[100010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string S;
	cin>>S;
	int ln=S.size();
	for(char i:S)ss[++n]=i-'a';
	int q;
	cin>>q;
	m=255;
	for(int i=1;i<=q;i++){
		string t;
		cin>>t>>ql[i]>>qr[i];
		ss[++n]=++m;sid[n]=-1;
		len[n]=t.size()+1;
		for(char j:t)ss[++n]=j-'a',sid[n]=i,len[n]=len[n-1]-1;
		len[n-t.size()]=0;
	}
	for(int i=1;i<=n;i++)cnt[rk[i]=ss[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;p<n;w<<=1,m=p){
		int cur=0;
		for(int i=n-w+1;i<=n;i++)id[++cur]=i;
		for(int i=1;i<=n;i++)if(sa[i]>w)id[++cur]=sa[i]-w;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)cnt[rk[i]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		p=0;
		memcpy(oldrk,rk,sizeof(rk));
		for(int i=1;i<=n;i++){
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
	}
	ss[n+1]=1919810; 
	for(int i=1,k=0;i<=n;i++){
		if(rk[i]==n)continue;
		if(k)k--;
		while(ss[i+k]==ss[sa[rk[i]+1]+k])k++;
		height[rk[i]]=k;
	}
	memset(cnt,0,sizeof(cnt));
	bt(1,1,ln);
	bool fl=0;
	for(int i=1;i<=n;i++){
		if(sid[sa[i]]>=1)cnt[sa[i]]=max(cnt[sa[i]],find(1,1,ln,ql[sid[sa[i]]],qr[sid[sa[i]]],(fl=0)));
		pd(1,height[i]);
		if(sid[sa[i]]==0)change(1,1,ln,sa[i],height[i]);
	}
	bt(1,1,ln);
	for(int i=n;i;i--){
		pd(1,height[i]);
		if(sid[sa[i]]>=1)cnt[sa[i]]=max(cnt[sa[i]],find(1,1,ln,ql[sid[sa[i]]],qr[sid[sa[i]]],(fl=0)));
		if(sid[sa[i]]==0)change(1,1,ln,sa[i],height[i-1]);
	}
	bt(1,1,q);
	for(int i=1;i<=n;i++){
		if(sid[sa[i]]>=1){
			cnt[sa[i]]=max(cnt[sa[i]],findp(1,1,q,sid[sa[i]]));
			change(1,1,q,sid[sa[i]],height[i]);
		}
		pd(1,height[i]);
	}
	for(int i=1;i<=n;i++)if(sid[i]>=1)ans[sid[i]]+=len[i]-cnt[i];
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}

Portal

我居然能独立AC NOI的黑题，后缀数组果然可爱

我们将命名串与所有的询问串，中间插上从未出现的字符然后放在一起跑SA。则对于来自询问串的某一条后缀$i$，我们需要求出一个数组$res_i$，表示所有出现在命名串以及该询问串中的后缀，与其$\operatorname{LCP}$的最大值。则对于一条询问串$T$，它的答案即为$\sum\limits_{i\in T}len_i-res_i$，其中$len_i$为后缀$i$的长度。

则现在问题被转换为求出所有的$res_i$。我们先考虑来自命名串的贡献。设当前我们讨论的后缀为$suf[i]$。则我们要求的即为区间$[l,r]$内所有后缀$suf[j]$，求$\min\Big(\operatorname{LCP}(suf[i],suf[j]),r-j+1\Big)$的最大值。

我们考虑二分这个最大值，设为$mid$。现在要来判断$mid$这个值是否合法。则只有区间$[l,l+mid-1]$中的$\operatorname{LCP}$才可能达到这么长，故只要找到其中的$\max\text{LCP}$，如果其长度大于等于$mid$，则$mid$合法。

到现在我们已经可以构思出一个$O(n\log^2n)$的二分套线段树的做法了。具体思路是，因为$\max\text{LCP}$一定在两个后缀的$rk$最接近时取到，所以我们将它拆成两半，一半是$rk_j\leq rk_i$的，一半是$rk_j\geq rk_i$的，并写两颗线段树分别维护。

则我们需要按顺序将位置插入线段树并统计答案，在前一棵中查询区间中$rk_i$的最大值，后一棵中查询$rk_i$的最小值（这里的线段树是以原串位置为下标的）。在查询到这个最大值/最小值后，就可以通过ST表求出$\text{LCP}$了。当然，这一切都是建立在二分的基础上，即，我们每次询问的区间都是二分出来的区间$[l,l+mid-1]$。

但是这样子得写两棵线段树，再加上ST表，太难受了。我们不如这样，直接在线段树上维护$\text{LCP}$长度。办法很简单，当新加入一个位置后，直接将线段树中所有$\text{LCP}$长度与它取$\min$即可。这样，ST表可以省掉了，两颗线段树要支持的操作也一致了（全局取$\min$，区间求$\max$）。

在这样写后，我们发现干脆连二分都可以省掉了（因为这里线段树的对应位置储存的值就是真实答案，所以可以省掉），直接在线段树上二分即可（这部分线段树上二分的代码比较神奇，建议看一下代码）。

（不知道大家有没有做过[HEOI2016/TJOI2016]字符串这道题，实际上思路是差不多的）。

然后就是来自该询问串内部的其它后缀的$\operatorname{LCP}$，这个也可以通过类似手法写出来。

则总复杂度$O(n\log n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2001000;
int n,m,q,t,id[N],res[N],len[N];
ll ans[N];
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],s[N];
char str[N];
bool mat(int a,int b,int k){
	if(y[a]!=y[b])return false;
	if((a+k<n)^(b+k<n))return false;
	if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
	return true;
}
void SA(){
	for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
	for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
	for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
	for(int k=1;k<n;k<<=1){
		int num=0;
		for(int i=n-k;i<n;i++)y[num++]=i;
		for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
		for(int i=0;i<=m;i++)buc[i]=0;
		for(int i=0;i<n;i++)buc[x[y[i]]]++;
		for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
		for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
		swap(x,y);
		x[sa[0]]=num=0;
		for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
		if(num>=n-1)break;
		m=num;
	}
	for(int i=0;i<n;i++)rk[sa[i]]=i;
	for(int i=0,k=0;i<n;i++){
		if(!rk[i])continue;
		if(k)k--;
		int j=sa[rk[i]-1];
		while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
		ht[rk[i]]=k;
	}
}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
#define change(x,y) seg[x].mn=min(seg[x].mn,y),seg[x].tag=min(seg[x].tag,y)
struct SegTree{
	int tag,mn;
}seg[N<<2];
void build(int x,int l,int r){
	seg[x].tag=0x3f3f3f3f,seg[x].mn=0;
	if(l!=r)build(lson,l,mid),build(rson,mid+1,r);
}
void pushdown(int x){
	change(lson,seg[x].tag),change(rson,seg[x].tag),seg[x].tag=0x3f3f3f3f;
}
void turnon(int x,int l,int r,int P,int val){
	if(l>P||r<P)return;
	seg[x].mn=max(seg[x].mn,val);
	pushdown(x);
	if(l!=r)turnon(lson,l,mid,P,val),turnon(rson,mid+1,r,P,val);
}
int getans(int x,int l,int r,int L,int R){
	if(l==r)return min(seg[x].mn,R-r+1);
	pushdown(x);
	if(seg[lson].mn>=R-mid+1)return getans(lson,l,mid,L,R);
	else return max(seg[lson].mn,getans(rson,mid+1,r,L,R));
}
int query(int x,int l,int r,int L,int R,bool &findans){
	if(l>R||r<L)return -1;
	if(L<=l&&r<=R){
		if(seg[x].mn>=R-r+1){findans=true;return getans(x,l,r,L,R);}
		return seg[x].mn;
	}
	pushdown(x);
	int tmp=query(lson,l,mid,L,R,findans);
	if(findans)return tmp;
	return max(tmp,query(rson,mid+1,r,L,R,findans));
}
int pointask(int x,int l,int r,int P){
	if(l>P||r<P)return 0;
	if(l==r)return seg[x].mn;
	pushdown(x);
	return pointask(lson,l,mid,P)+pointask(rson,mid+1,r,P);
}
pair<int,int>p[500100];
void read(int &x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); 
}
int main(){
	scanf("%s",str),t=strlen(str);for(int i=0;i<t;i++)s[n++]=str[i]-'a'+1;
	read(q);
	for(int i=1;i<=q;i++){
		scanf("%s",str),read(p[i].first),read(p[i].second),m=strlen(str),p[i].first--,p[i].second--;
		id[n]=-1,s[n]=i+26,n++;
		for(int j=0;j<m;j++)id[n]=i,s[n]=str[j]-'a'+1,len[n]=m-j,n++;
	}
	m=q+26;
	SA();
	bool tmp;
	build(1,0,t-1);
	for(int i=1;i<n;i++){
		change(1,ht[i]);
		if(!id[sa[i-1]])turnon(1,0,t-1,sa[i-1],ht[i]);
		if(id[sa[i]]>=1)tmp=false,res[sa[i]]=max(res[sa[i]],query(1,0,t-1,p[id[sa[i]]].first,p[id[sa[i]]].second,tmp));
	}
	build(1,0,t-1);
	for(int i=n-1;i>=0;i--){
		if(id[sa[i]]>=1)tmp=false,res[sa[i]]=max(res[sa[i]],query(1,0,t-1,p[id[sa[i]]].first,p[id[sa[i]]].second,tmp));
		change(1,ht[i]);
		if(!id[sa[i]])turnon(1,0,t-1,sa[i],ht[i]);
	}
	build(1,1,q);
	for(int i=1;i<n;i++){
		change(1,ht[i]);
		if(id[sa[i-1]]>=1)turnon(1,1,q,id[sa[i-1]],ht[i]);
		if(id[sa[i]]>=1)res[sa[i]]=max(res[sa[i]],pointask(1,1,q,id[sa[i]]));
	}
	for(int i=0;i<n;i++)if(id[i]>=1)ans[id[i]]+=len[i]-res[i];
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}