Description：

给你 $n$ 个串，多次询问第 $i$ 个串在第 $[L,R]$ 个串中共出现了多少次。

$1\leqslant n,q,\sum|s_i|\leqslant 2\times 10^5$

Solution：

先把所有串建出 $AC$ 自动机，那么某个节点所代表的字符串就在 $fail$ 树的子树中的节点中出现过，那么我们就可以求出 $fail$ 树的 $dfn$ 序，并以 $1\sim n$ 为 $X$ 轴， $dfn$ 序为 $Y$ 轴建立主席树，每个位置在上一个位置的主席树上把这个串在 $trie$ 树上的所有祖先的 $dfn$ 位置都加一，查询时就是查询 $[L,R]$ 中 $dfn$ 在子树区间内的和。

为什么暴力在 $trie$ 树上跳祖先复杂度是对的？因为插入的时候就是沿着这个插入的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,q;

#define MAXN 200010

int pos[MAXN];

char c[MAXN];

namespace ACAM

{

	struct node

	{

		int tr[26];

		int fa,fail;

		int tag;

	}t[MAXN];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root = 0;

	void insert(char c[],int id)

	{

		int cur = root;

		int l = strlen(c + 1);

		for(int i = 1;i <= l;++i)

		{

			if(t[cur].tr[c[i] - 'a'] == 0)

				t[cur].tr[c[i] - 'a'] = newnode();

			t[t[cur].tr[c[i] - 'a']].fa = cur;

			cur = t[cur].tr[c[i] - 'a'];

		}

		pos[id] = cur;

		return;

	}

	void makefail()

	{

		queue<int> q;

		for(int i = 0;i < 26;++i)

			if(t[root].tr[i] != 0)

				q.push(t[root].tr[i]);

		while(!q.empty())

		{

			int k = q.front();q.pop();

			for(int i = 0;i < 26;++i)

			{

				if(t[k].tr[i] != 0)

				{

					t[t[k].tr[i]].fail = t[t[k].fail].tr[i];

					q.push(t[k].tr[i]);

				}

				else

				{

					t[k].tr[i] = t[t[k].fail].tr[i];

				}

			}

		}

		return;

	}

}

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dfn[MAXN],siz[MAXN],tot = 0;

bool v[MAXN];

void dfs(int k)

{

	v[k] = true;

	dfn[k] = ++tot;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dfs(e[i].to);

		siz[k] += siz[e[i].to];

	}

	return;

}

namespace PST 

{

	struct node

	{

		int lc,rc;

		int sum;

	}t[MAXN * 30];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root[MAXN];

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void insert(int &rt,int p,int l,int r)

	{

		int k = newnode();t[k] = t[rt];rt = k;

		++t[rt].sum;

		if(l == r)return;

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		return;

	}

	int calc(int rt,int L,int R,int l,int r)

	{

		if(rt == 0)return 0;

		if(L <= l && r <= R)return t[rt].sum;

		int res = 0;

		if(L <= mid)res += calc(t[rt].lc,L,R,l,mid);

		if(R > mid)res += calc(t[rt].rc,L,R,mid + 1,r);

		return res;

	}

}

int main()

{

	scanf("%d%d",&n,&q);

	for(int i = 1;i <= n;++i)

	{

		scanf("%s",c + 1);

		ACAM::insert(c,i);

	}

	ACAM::makefail();

	for(int i = 1;i <= ACAM::ptr;++i)add(ACAM::t[i].fail,i);

	dfs(0);

	PST::build(PST::root[0],1,tot);

	for(int i = 1;i <= n;++i)

	{

		PST::root[i] = PST::root[i - 1];

		for(int cur = pos[i];cur != 0;cur = ACAM::t[cur].fa)

			PST::insert(PST::root[i],dfn[cur],1,tot);

	}

	int l,r,k;

	for(int i = 1;i <= q;++i)

	{

		l = rd();r = rd();k = rd();

		int L = dfn[pos[k]],R = dfn[pos[k]] + siz[pos[k]] - 1;

		int ans = PST::calc(PST::root[r],L,R,1,tot) - PST::calc(PST::root[l - 1],L,R,1,tot);

		printf("%d\n",ans);

	}

	return 0;

}