LINK：子序列自动机
想了一些很有趣的做法。
dp 容易看出 f[i][j]表示前i个数匹配了j个数的dp 不过复杂度很高。
贪心 容易想到匹配的时候每个数字尽量往前匹配 这样显然是最优的 复杂度Qn.
可以发现 这个贪心显然可以优化 我们无非是要寻找下一个离当前位置最近的一个位置。
动态开点线段树存每个值得位置 查询的时候 先ask一下区间和 然后线段树上二分即可。
容易想到主席树 显然可以倒着建立主席树每次更新某个点的位置 查询的时候可以直接查。
不过需要考虑一下子序列自动机 我们期望建立一个自动机来识别所有的子序列。
可以发现随便连点即可。优化的话也不过就是贪心的优化思路。
再次来到如何贪心的地方 容易发现将位置集合放到vector里然后二分即可。
如果待修呢？平衡树做这个东西就行了。
由于建立这个自动机空间和时间花销过大 我们可以不建立 直接使用算法进行匹配即可。
int n,m,Q,T;
vector<int>g[MAXN];
vector<int>::iterator it;
int main()
{
freopen("1.in","r",stdin);
get(T);get(n);get(Q);get(m);
rep(1,n,i){int get(x);g[x].pb(i);}
rep(1,Q,i)
{
int get(x),flag=0,st=0;
rep(1,x,j)
{
int get(y);
if(flag)continue;
it=lower_bound(g[y].begin(),g[y].end(),st+1);
if(it==g[y].end()){flag=1;continue;}
st=*it;
}
if(!flag)puts("Yes");
else puts("No");
}
return 0;
}