0 #P3207. 花神的嘲讽计划Ⅰ

    ID: 2389 传统题 1000ms 128MiB 尝试: 4015 已通过: 839 难度: 6 上传者: 标签>字符串字符串哈希数据结构CF2000可持久化线段树二分可持久化数据结构

花神的嘲讽计划Ⅰ

花神的嘲讽计划Ⅰ

题目描述

DJ 准备了一个长度为 nn 的讲课方案,每个数表示他在相应时刻讲的内容。花神准备了 mm 个嘲讽方案,每个都是长度为 kk 的数列,并指定一个检查区间 [x,y][x,y]。

若 DJ 的讲课数列在 [x,y][x,y] 内没有按原顺序连续出现该方案,DJ 就会感到尴尬。整个出现位置都必须在区间内。例如,区间长度小于 kk 时,方案一定没有出现。

请判断每个嘲讽方案是否会让 DJ 尴尬。

输入格式

第一行包含三个整数 n,m,kn,m,k,分别表示讲课数列长度、查询次数和每个方案的长度。

第二行包含 nn 个整数,表示 DJ 的讲课数列。

接下来 mm 行,每行先给出两个整数 x,yx,y(1≤x≤y≤n1\le x\le y\le n),再给出 kk 个整数,表示在该区间内检查的方案。

所有输入整数不超过 2×1092\times 10^9,方案序列中的每个数字不超过 nn。

输出格式

对每个方案依次输出一行。若该方案没有在指定区间内连续出现,输出 Yes,否则输出 No。

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

样例解释

第一个和第五个方案完整出现在各自的区间内。第二个方案的顺序不同,第三个和第四个方案都只在越出相应区间的位置出现。

题目作者为 Memphis。