题面描述丢失了。。。
给n个串模板串，然后再给你m个串，对于这m个串的每个串，问在[L,R]的模板串中，在多少个串中出现过;
这题的正解是对于后m个串建AC自动机，然后离线，在fail树上树链求并。
然而我想脑抽地打一下后缀数组；
如果用后缀数组的话，跟喵星球上的点名差不多，但是要在[L,R]中，所以可以用Gty的二逼妹子序列一样的套路，把权值分块而不用树状数组；
这样可以做到nsqrt(n);但是由于串有几百万长，求SA就T了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define RG register
using namespace std;
const int N=2000050;
struct data{
int fir,sec,id;
}x[N];
bool cmp(const data &a,const data &b){
if(a.fir==b.fir) return a.sec<b.sec;
else return a.fir<b.fir;
}
int y[N],sa[N],height[N],rnk[N],rk,n,m,len;
int pos[N],fr[N],bel[N],blockans[N],sum[N],st[N],block,block2,L[N],R[N],pre[N],pre2[N],ST[N][21];
int ans[N],lo[N],tong[N],g[N],cnt1,ll[N],rr[N];
struct date{
int l,r,lx,rx,id;
}q[N];
bool Cmp(const date &a,const date &b){
if(pos[a.l]==pos[b.l]) return a.r<b.r;
else return pos[a.l]<pos[b.l];
}
char a[N],s[N];
void work2(){
rk=1;y[x[1].id]=rk;
for(RG int i=2;i<=len;i++){
if(x[i-1].fir!=x[i].fir||x[i-1].sec!=x[i].sec) rk++;
y[x[i].id]=rk;
}
}
void work(){
sort(x+1,x+1+len,cmp);work2();
for(RG int i=1;i<=len;i<<=1){
for(RG int j=1;j+i<=len;j++) x[j].id=j,x[j].fir=y[j],x[j].sec=y[j+i];
for(RG int j=len-i+1;j<=len;j++) x[j].id=j,x[j].fir=y[j],x[j].sec=0;
sort(x+1,x+1+len,cmp);work2();
if(rk==len) break;
}
for(RG int i=1;i<=len;i++) sa[y[i]]=i;
}
void get_height(){
int kk=0;for(int i=1;i<=len;i++) rnk[sa[i]]=i;
for(RG int i=1;i<=len;i++){
if(kk) kk--;
int j=sa[rnk[i]-1];
while(a[i+kk]==a[j+kk]) kk++;
height[rnk[i]]=kk;
}
}
void make_ST(){
pre[0]=1;for(RG int i=1;i<=20;i++) pre[i]=pre[i-1]<<1;
pre2[0]=-1;for(RG int i=1;i<=len;i++) pre2[i]=pre2[i>>1]+1;
for(RG int i=2;i<=len;i++) ST[i][0]=height[i];
for(RG int j=1;j<=20;j++)
for(RG int i=2;i<=len;i++){
if(i+pre[j]-1<=len){
ST[i][j]=min(ST[i][j-1],ST[i+pre[j-1]][j-1]);
}
}
}
int query(int l,int r){
if(l>r) swap(l,r);
int x=pre2[r-l+1];
return min(ST[l][x],ST[r-pre[x]+1][x]);
}
int LCP(RG int l,RG int r){
if(l==r) return len-sa[l];
if(l>r) swap(l,r);
return query(l+1,r);
}
int get_l(RG int x,RG int le){
int ret=x,l=1,r=x;
while(l<=r){
int mid=(l+r)>>1;
if(LCP(x,mid)>=le) ret=mid,r=mid-1;
else l=mid+1;
}
return ret;
}
int get_r(RG int x,RG int le){
RG int ret=x,l=x,r=len;
while(l<=r){
RG int mid=(l+r)>>1;
if(LCP(x,mid)>=le) ret=mid,l=mid+1;
else r=mid-1;
}
return ret;
}
void update(RG int x,RG int val){tong[x]+=val;}
int ask(RG int l,RG int r){
RG int ret=0;
if(bel[l]==bel[r]){
for(RG int i=l;i<=r;i++) if(tong[i]) ret++;
}
else{
for(RG int i=l;i<=rr[bel[l]];i++) if(tong[i]) ret++;
for(RG int i=ll[bel[r]];i<=r;i++) if(tong[i]) ret++;
for(RG int i=bel[l]+1;i<=bel[r]-1;i++) ret+=blockans[i];
}
return ret;
}
void Modui(){
block=sqrt(len);for(RG int i=1;i<=len;i++) pos[i]=(i-1)/block+1;
block2=sqrt(N-1);for(RG int i=1;i<=N-1;i++) bel[i]=(i-1)/block2+1;
if((N-1)%block2) cnt1=(N-1)/block2+1;
else cnt1=(N-1)/block2;
for(RG int i=1;i<=cnt1;i++) ll[i]=(i-1)*block2+1,rr[i]=i*block2;
sort(q+1,q+1+m,Cmp);
for(RG int l=1,r=0,i=1;i<=m;i++){
while(l>q[i].l){l--;update(g[l],1);if(tong[g[l]]==1)blockans[bel[g[l]]]++;}
while(r<q[i].r){r++;update(g[r],1);if(tong[g[r]]==1)blockans[bel[g[r]]]++;}
while(l<q[i].l){update(g[l],-1);if(tong[g[l]]==0)blockans[bel[g[l]]]--;l++;}
while(r>q[i].r){update(g[r],-1);if(tong[g[r]]==0)blockans[bel[g[r]]]--;r--;}
ans[q[i].id]=ask(q[i].lx,q[i].rx);
}
}
int main(){
freopen("substr.in","r",stdin);
freopen("substr.out","w",stdout);
scanf("%d%d",&n,&m);
for(RG int i=1;i<=n;i++){
scanf("%s",s+1);int le=strlen(s+1);
for(RG int j=1;j<=le;j++) a[++len]=s[j],fr[len]=i;
a[++len]='#',fr[len]=N-1;
}
for(RG int i=1;i<=m;i++){
scanf("%d%d",&L[i],&R[i]);scanf("%s",s+1);
int le=strlen(s+1);lo[i]=le;st[i]=len+1;
for(RG int j=1;j<=le;j++) a[++len]=s[j],fr[len]=i+n;
a[++len]='#',fr[len]=N-1;
}
for(RG int i=1;i<=len;i++) x[i].id=i,x[i].fir=x[i].sec=a[i]-'a'+1;
work();get_height();make_ST();
for(RG int i=1;i<=m;i++){
int l=get_l(rnk[st[i]],lo[i]),r=get_r(rnk[st[i]],lo[i]);
q[i].l=l,q[i].r=r,q[i].lx=L[i],q[i].rx=R[i],q[i].id=i;
}
for(RG int i=1;i<=len;i++) g[i]=fr[sa[i]];
Modui();for(int i=1;i<=m;i++) printf("%d
",ans[i]);
}