子串看起来就很SuffixStructures
于是上SAM
本来想着直接LCT
后来发现没法串定位（暴力匹配复杂度不对）
然后就离线吧，先建出来然后链加子树和，树剖就odk。
其实更直接的套路是线段树合并right集合维护。
这个题很像BZOJ3881 那个题更复杂一点，需要树链的并（到时候看看这个题可不可以加强一下扔到校内模拟赛
当然还有正确的ACA写法，直接FAIL树上主席树。（就更像BZOJ3881了
（但感觉都很暴力，我的想法貌似还挺好的）
顺便学习了广义SAM的正确写法。（发现之前的写法死活改不对
//Love and Freedom. #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ll long long #define inf 20021225 #define N 200010 #define pb push_back using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } struct node{int ch[26],fa,len;}t[N<<1]; struct edge{int to,lt;}e[N<<1]; int lt,poi,cnt,rt,ed[N],in[N<<1]; vector<int> endpos; void insert(int c,int id) { if(t[lt].ch[c]) { int p=lt,np=lt=t[p].ch[c]; if(t[np].len==t[p].len+1) ed[id]=np,endpos.pb(np); else { int nq=++poi; ed[id]=nq; endpos.pb(nq); t[nq].len=t[p].len+1; memcpy(t[nq].ch,t[np].ch,sizeof(t[np].ch)); t[nq].fa=t[np].fa; t[np].fa=nq; for(;p&&t[p].ch[c]==np;p=t[p].fa) t[p].ch[c]=nq; lt=nq; } return; } int p=lt,np=lt=++poi; endpos.pb(np); ed[id]=np; t[np].len=t[p].len+1; for(;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=np; if(!p){t[np].fa=rt; return;} int q=t[p].ch[c]; if(t[q].len==t[p].len+1){t[np].fa=q; return;} int nq=++poi; t[nq].fa=t[q].fa; t[q].fa=t[np].fa=nq; memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch)); t[nq].len=t[p].len+1; for(;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=nq; } #define lowbit(x) (x&-x) int tr[N<<1]; void add(int x,int v){while(x<=poi) tr[x]+=v,x+=lowbit(x);} void modify(int l,int r,int v){add(l,v); add(r+1,-v);} int query(int x){int a=0; while(x) a+=tr[x],x-=lowbit(x); return a;} int dfn[N<<1],tot,sz[N<<1],son[N<<1],idfn[N<<1],top[N<<1],fa[N<<1]; void addedge(int x,int y){e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;} void build(){for(int i=2;i<=poi;i++) addedge(t[i].fa,i);} void dfs(int x,int fr) { fa[x]=fr; sz[x]=1; for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; dfs(y,x); sz[x]+=sz[y]; if(sz[y]>=sz[son[x]]) son[x]=y; } } void dfs2(int x,int t) { top[x]=t; dfn[x]=++tot; idfn[tot]=x; if(!son[x]) return; dfs2(son[x],t); for(int i=in[x];i;i=e[i].lt) if(e[i].to!=son[x]) dfs2(e[i].to,e[i].to); } void modify(int x,int v) { while(x) modify(dfn[top[x]],dfn[x],v), x=fa[top[x]]; } int ask(int x){return query(dfn[x]);} #define Q 500010 int n,q; char ch[N]; int ans[Q],pre[N]; struct qry{int id,opt,pos,x;}r[Q<<1]; int qwq; bool operator<(qry a,qry b){return a.pos<b.pos;} int main() { n=read(),q=read(); poi=rt=lt=1; int tot=0; for(int i=1;i<=n;i++) { scanf("%s",ch+1); lt=rt; int sn=strlen(ch+1); for(int j=1;j<=sn;j++) ++tot,insert(ch[j]-'a',i); pre[i]=tot; } int L,R,K; build(); dfs(1,0); dfs2(1,1); for(int i=1;i<=q;i++) L=read(),R=read(),K=read(), r[++qwq].id=i,r[qwq].opt=-1,r[qwq].pos=pre[L-1],r[qwq].x=ed[K], r[++qwq].id=i,r[qwq].opt=1,r[qwq].pos=pre[R],r[qwq].x=ed[K]; int p=1; sort(r+1,r+qwq+1); while(p<=qwq&&!r[p].pos) p++; for(int i=0;i<endpos.size();i++) { int pos=endpos[i]; modify(pos,1); while(p<=qwq&&r[p].pos==i+1) ans[r[p].id]+=r[p].opt*ask(r[p].x),p++; } for(int i=1;i<=q;i++) printf("%d\n",ans[i]); return 0; }