题目描述

Description

霸中智力测试机构的一项工作就是按照一定的规则删除一个序列的数字，得到一个确定的数列。Lyx很渴望成为霸中智力测试机构的主管，但是他在这个工作上做的并不好，俗话说熟能生巧，他打算做很多练习，所以他希望你写一个程序来快速判断他的答案是否正确。

Input

第一行为一个整数m（1<=m<=1000000）第二行包括m个用空格分开的整数ai（1<=ai<=1000000），组成了最初的序列，第三行为一个整数n（1<=n<=1000000），表示n个Lyx经过一系列删除得到的序列，每个序列两行，第一行给出长度L（1<=L<=m），然后下一行为L个由空格分开的整数bi（1<=bi<=1000000）。

Output

共n行，如果Lyx的序列确实是由最初的序列删除一些数得到，就输出TAK，否则输出NIE。

Sample Input

7
1 5 4 5 7 8 6
4
5
1 5 5 8 6
3
2 2 2
3
5 7 8
4
1 5 7 4

Sample Output

TAK
NIE
TAK
NIE

题目分析

因为ai不大 先将原序列每个数字的位置存储起来
然后枚举Lyx的每个数字 贪心的想 如果能匹配上原数列的某个位置 一定尽可能靠前给别的数字创造机会
所以记录当前位置 在vector上二分

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
vector<int> s[1000010];
vector<int>::iterator it;
int a[1000010];
int main()
{
    scanf("%d",&n);
    for(int x,i=1;i<=n;i++) 
        scanf("%d",&x),s[x].push_back(i);
    scanf("%d",&m);
    while(m--)
    {
        int tm;
        scanf("%d",&tm);
        for(int i=1;i<=tm;i++) scanf("%d",&a[i]);
        int now=0,o;
        for(o=1;o<=tm;o++)
        {
            it=upper_bound(s[a[o]].begin(),s[a[o]].end(),now);
            if(it==s[a[o]].end()) break;
            now=*it; 
        }
        if(o>tm) printf("TAK\n");
        else printf("NIE\n");
    }
}