Description：

有 $n$ 个字符串 $S_1,S_2,\dots,S_n$ 和一个字符串集合 $T$ ，有 $q$ 个操作，往 $T$ 集合里添加一个字符串和询问集合 $T$ 中有多少个字符串包含 $S_x$ 。

$1\leqslant n,q\leqslant 10^5,$ 字符串总长 $\leqslant 2\times 10^6$

Solution：

$T$ 集合是变动的肯定是对 $S$ 建一个 $AC$ 自动机，然后每次插入一个 $T$ 中的字符串，在 $S$ 的 $trie$ 树上从根到这个字符串对应节点这条链上所有的点在 $fail$ 树上的祖先都会答案加一，但是如果直接加会算重，所以可以用树链的并的做法，对于相邻两条从某个点到根的路径，减去他们的 $LCA$ 到根的路径，这样每个点只会被算一遍，树上路径加肯定可以树剖 $+$ 线段树或者 $LCT$ 来 $O(\log^2n)$ 或 $O(\log n)$ 做，但是会 $TLE$ ，这题有一个重要启发意义就是树上差分是可以在线的，先该怎么差分就怎么差分，然后反正树上差分的核心操作是求子树和，所以可以用一个树状数组就可以在线树上差分了。

关于到根的树链的并怎么求，可以把所有树链拿出来，按 $dfs$ 序排序，然后把所有树链加一，然后再把相邻的 $LCA$ 到根的链减一，可以证明这样就是树链的并。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define MAXL 2000010

char s[MAXL];

int pos[MAXN];

struct node

{

	int tr[26];

	int fail;

	node(){memset(tr,0,sizeof(tr));}

}t[MAXL];

int ptr = 0;

int root = 0;

int newnode(){return ++ptr;}

void insert(char c[],int id)

{

	int l = strlen(c + 1);

	int cur = root;

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

	{

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

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

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

	}

	pos[id] = cur;

	return;

}

void make_fail()

{

	queue<int> q;

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

	{

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

		{

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

			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[MAXL << 1];

int edgenum = 0;

int lin[MAXL] = {0};

void adde(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int fa[MAXL],dep[MAXL],top[MAXL],siz[MAXL],son[MAXL],rnk[MAXL],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

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

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

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

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;rnk[k] = ++tot;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

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

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int lowbit(int x){return x & (-x);}

int c[MAXL];

void add(int p,int k){for(int i = p;i <= tot;i += lowbit(i))c[i] += k;return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

int st[MAXL],stop = 0;

bool cmp(int a,int b){return rnk[a] < rnk[b];}

void mark(char c[])

{

	int l = strlen(c + 1);

	int cur = root;

	stop = 0;

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

	{

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

		st[++stop] = cur;

	}

	sort(st + 1,st + 1 + stop,cmp);

	int last = 0;

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

	{

		if(i == 1 || st[i] != st[i - 1])

		{

			add(rnk[st[i]],1);

			int lca = LCA(st[i],last);

			add(rnk[lca],-1);

			last = st[i];

		}

	}

	return;

}

int calc(int k)

{

	int p = pos[k];

	return query(rnk[p] + siz[p] - 1) - query(rnk[p] - 1);

}

int main()

{

	scanf("%d",&n);

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

	{

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

		insert(s,i);

	}

	make_fail();

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

	{

		adde(i,t[i].fail);

	}

	dfs1(0,0);dfs2(0,0);

	scanf("%d",&m);

	int opt,x;

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

	{

		scanf("%d",&opt);

		if(opt == 1)

		{

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

			mark(s);

		}

		else

		{

			scanf("%d",&x);

			printf("%d\n",calc(x));

		}

	}

	return 0;

}