题解

题目类型：离线预处理 + 多次查询 + 二分
核心任务：判断每个查询序列 b[1..m] 是否是原序列 a[1..n] 的子序列（subsequence）。

一、思路概述

把原序列 a 的每个数值出现的位置全部记录下来，按下标升序存到桶 e[value] 中。
对于每个查询序列 b，从左到右扫描 b[i]，在对应的 e[b[i]] 里用二分查找第一个严格大于当前 pos 的位置，找到则把 pos 更新为该位置；若找不到，则说明 b 不是 a 的子序列。

这是经典的“子序列判定（多查询）”做法：
预处理 O(n)，每个查询 O(m log occ)，其中 occ 是对应值在 a 中的出现次数。

二、关键实现

• mp[x]：值 x 是否在 a 中出现过的布尔标记（可做快速剪枝）。
• e[x]：存放值为 x 的所有出现下标，天然有序（因为输入 a 时按顺序 push_back）。
• check(pos, x)：给定当前下标上界 pos，在 e[x] 中二分找到第一个大于 pos 的下标，并把 pos 更新为该下标。若不存在，返回 false。

特殊剪枝：

• 若 m > n，显然不可能是子序列，直接输出 NIE。

三、正确性说明

• 子序列定义要求保序且逐个匹配。
• 对每个 b[i] 在 a 中寻找严格靠后的首次出现位置，即“下一个匹配点”。
• 二分查找保证每步找到的是最早可行位置，从而全局可行当且仅当每一步都有解。

四、复杂度

• 预处理：将 a 扫一遍并入桶，O(n)。
• 每次查询：对 m 个元素分别在其桶中二分，O(m log occ)，总体 O(Σ m log occ)。
• 适合大量查询与较大数据范围。

五、与代码对应

• 读入 a：置 mp[a]=1 并 e[a].push_back(i)。
• 每个查询：
  • 若 m>n，直接 NIE；
  • 否则依次调用 check(pos, b[i])，失败则 NIE，全部成功则 TAK。

六、代码（题给）

#include<bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
using namespace std;

const int N=1e6+10;
int q,n,b[N];
bool mp[N];
vector<int> e[N]; 

bool check(int &pos,int x){
	int l=0,r=e[x].size()-1;
	if(l>r)return 0;
	bool flag=0;
	int tmp=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(e[x][mid]>pos){
			flag=1;
			tmp=e[x][mid];
			r=mid-1;
		}else l=mid+1;
	}
	pos=tmp;
	return flag;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;
	rep(i,1,n){
		int a;
		cin>>a;
		mp[a]=1;
		e[a].push_back(i);
	}
	cin>>q;
	while(q--){
		int m;
		cin>>m;
		rep(i,1,m){
			cin>>b[i];
		}
		int pos=0;
		bool flag=1;
		if(m>n){
			cout<<"NIE\n";
			continue;
		}
		rep(i,1,m){
			if(!mp[b[i]]){
				flag=0;
				break;
			}
			flag=check(pos,b[i]);
			if(!flag)break;
		}
		if(!flag){
			cout<<"NIE\n";
		}else{
			cout<<"TAK\n";
		}
	}
	return 0;
}