标签：二分，模拟
题目
题目描述
PTY 进行 IQ 测试，测试的项目是判断一个序列是否是另外一个序列删除若干个数字之后得 到的，PTY 深知自己的 IQ 低于 sqrt(-1)，所以他请来了智商超高的你来替他解决问题。
输入
第一行为一个整数 n，第二行包括 n 个用空格分开的整数 ai，组成 了最初的序列，第三行 为一个整数m，表示n个IQ测试询问的序列，每个序列两行，第一行给出长度L（1<=L<=n）， 然后下一行为 L 个由空格分开的整数 bi。
输出
共 m 行，如果询问的序列确实是由最初的序列删除一些数得到，就输出 TAK，否则输出 NIE。
样例输入
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
样例输出
TAK
NIE
TAK
NIE
提示
对于 30%的数据 n<=1000,m<=1000 对于 100%的数据 1<=ai,bi<=1000000，∑L<=1000000，n,m<=1000000
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
//**********head by yjjr**********
const int maxn=2e6+6;
int v[maxn],L[maxn],R[maxn],a[maxn],b[maxn],n,m,len,sum[maxn];
inline int find(int x,int y){
if(!L[y])return -1;
int l=L[y],r=R[y];
while(l<r)if(v[mid]>x)r=mid;else l=mid+1;
if(v[l]>x)return v[l];else return -1;
}
int main()
{
n=read();
rep(i,1,n)a[i]=read(),sum[a[i]]++;
rep(i,1,maxn)sum[i]+=sum[i-1];
dep(i,n,1)v[sum[a[i]]--]=i;
rep(i,1,n){
int t=a[v[i]],l=a[v[i-1]];
if(t!=l)L[t]=i,R[l]=i-1;
}
R[a[v[n]]]=n;
m=read();
while(m--){
bool flag=1;int pos=0,x;
len=read();
rep(i,1,len){
x=read();
pos=find(pos,x);
if(pos==-1){flag=0;x=i;break;}
}
if(!flag)rep(i,x+1,len)x=read();
if(flag)puts("TAK");else puts("NIE");
}
}
