Description：

给一个长为 $n$ 的模板数列和 $m$ 个数列，判断每个数列能否由模板数列删去几个数字得到。

$1\le n ,m\le1000000 $

Solution：

题目没有给模板数列之外的数列长度，也就是说需要一个 $O($ 读入 $)$ 的做法，显然暴力匹配是 $O(nm)$ 的，如果一个一个考虑的话，最慢还是会遍历，所以正解一定是把所有数列放在一起操作，按照但字符串序列匹配的思想，如果当前模板串数字为 $x$ ，那么就把所有当前处理到 $x$ 的数列都一起往后移一步，如果移出去了，就说明找到了一个，这个可以用 $vector$ 开个桶记录所有当前位是这个的数列，每次把当前 $vector$ 清空，在数列下一位对应 $vector$ 里加入数列即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<vector>

using namespace std;

int n;

#define MAXN 1000010

int t[MAXN];

int m,l;

vector<int> v[MAXN],b[MAXN];

int c[MAXN];

bool ans[MAXN];

int s[MAXN],top = 0;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&t[i]);

	scanf("%d",&m);

	int x;

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

	{

		scanf("%d",&l);

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

		{

			scanf("%d",&x);

			b[i].push_back(x);

		}

		v[b[i][0]].push_back(i);

		c[i] = 0;

	}

	memset(ans,false,sizeof(ans));

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

	{

		for(int k = 0;k < v[t[i]].size();++k)

		{

			x = v[t[i]][k];

			++c[x];

			if(c[x] >= b[x].size())ans[x] = true;

			else s[++top] = x;

		}

		v[t[i]].clear();

		while(top > 0)

		{

			x = s[top--];

			v[b[x][c[x]]].push_back(x);

		}

	}

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

	{

		if(ans[i])puts("TAK");

		else puts("NIE");

	}

	return 0;

}