一开始以为是个神题后来发现是个大水题。。。
next[i][j]表示数字i在原序列中出现第j次的位置,now用来记录对于当前的b[i],最小的合法位置是多少。每次二分更新now,如果now>n说明在原序列中没有合法的b[i]存在,直接退出。
二分必须要手写,因为vector里用lower_bound返回的并不是下标值而是迭代器(具体是什么我也不清楚)。
PS:机房小伙伴用倍增的方法写但是超时了,并不知道为什么。二分大法好!
#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> using namespace std; #define pb push_back const int N=1000005; vector<int> next[N]; int n,m,l,a[N],b[N],now; bool can; inline int get(){ int p=0;char x=getchar(); while (x<'0' || x>'9') x=getchar(); while (x>='0' && x<='9') p=p*10+x-'0',x=getchar(); return p; } inline int BS(int t,int k){ int l=0,r=next[t].size()-1,mid,ret=n+1; while (l<=r) { mid=(l+r)>>1; if (next[t][mid]>k) ret=mid,r=mid-1; else l=mid+1; } if (ret==n+1) return ret; else return next[t][ret]; } int main(){ n=get(); for (int i=1;i<=n;i++){ a[i]=get(); next[a[i]].pb(i); } m=get(); while (m--){ l=get();now=0;can=1; for (int i=1;i<=l;i++) b[i]=get(); for (int i=1;i<=l;i++){ now=BS(b[i],now);//更新now if (now>n) { can=0; break; } } if (can) printf("TAK\n"); else printf("NIE\n"); } return 0; }