Mars_Cat

Description

Input

Output

Sample Input

Sample Output

HINT

Source

这题似乎网上都用的是Hash+可持久化线段树。。。看起来好难啊。本蒟蒻似乎并不怎么会。。
然而还要完成字符串训练好题。。

后来呢。。 就没有后来了。。想了乱七八糟的方法A掉了这题= =|用一个东西存储Hash值。再乱搞记录下每个Hash开头的位置（哼。有k的值一切都那么美好。。）
最后只要查找要求的东西在不在范围内有一份就好啦！蛤蛤蛤。。真是太聪明啦。。（大雾）

想到了平衡树套平衡树。。再想想自己用的并不熟练。于是就有了 跳表套跳表 算法。。

代码如下：（用VisualStudio编的。。有点奇怪的东西）

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef pair<ull, ull> puu;
#define X first
#define Y second
#define mp make_pair
const int mul = 97;
const ull Mod = 10000007;
const int Inf = 10000000;

bool operator < (const puu & x, const puu & y) { if (x.X == y.X)return x.Y<y.Y;return x.X<y.X; }
bool operator <= (const puu & x, const puu & y) { if (x.X == y.X)return x.Y <= y.Y;return x.X <= y.X; }
bool operator > (const puu & x, const puu & y) { if (x.X == y.X)return x.Y>y.Y;return x.X>y.X; }
bool operator >= (const puu & x, const puu & y) { if (x.X == y.X)return x.Y >= y.Y;return x.X >= y.X; }
bool operator == (const puu & x, const puu & y) { return x.X == y.X && x.Y == y.Y; }

int n, m, k, xx, yy;
int a[200010];
ull cc = 1, cc1 = 1;
puu x;

const int maxlev = 20;
struct node { int x;node *Nxt[maxlev]; };
struct Skip { node *bgn, *ed; };
struct node_ { puu num;node_ *Nxt[maxlev];Skip Lst; };
struct Skip_ { node_ *Bgn, *Ed; }List;
int RandLev() { int i = 0;for (;rand() & 1;++i)if (i >= maxlev)return maxlev - 1;return i; }

void Init_List()
{
	List.Bgn = new node_; List.Ed = new node_;
	List.Bgn->num = mp(0, 0); List.Ed->num = mp(-1, -1);
	for (int i = 0;i<maxlev;++i)List.Bgn->Nxt[i] = List.Ed;
}
void Init_List(node_ *Mm)
{
	Mm->Lst.bgn = new node; Mm->Lst.ed = new node;
	Mm->Lst.bgn->x = -Inf;
	Mm->Lst.ed->x = Inf;
	for (int i = 0;i<maxlev;++i)Mm->Lst.bgn->Nxt[i] = Mm->Lst.ed;
}
void Add(node_ *Mm, int xx)
{
	int k = RandLev();
	node *now = Mm->Lst.bgn;
	for (int i = maxlev - 1;i >= 0;--i)
	{
		while (xx >= now->Nxt[i]->x)now = now->Nxt[i];
		if (now->x == xx)return;
	}
	now = Mm->Lst.bgn;
	node *tmp = new node;
	tmp->x = xx;
	for (int i = maxlev - 1;i >= 0;--i)
	{
		while (xx > now->Nxt[i]->x)now = now->Nxt[i];
		if(i<=k)
		{
			tmp->Nxt[i] = now->Nxt[i];
			now->Nxt[i] = tmp;
		}
	}
}
void Add(puu xx, int Pos)
{
	int k = RandLev();
	node_ *now = List.Bgn;
	bool Flag = false;
	for (int i = maxlev - 1;i >= 0;--i)
	{
		while (xx >= now->Nxt[i]->num)now = now->Nxt[i];
		if (now->num == xx)
		{
			Add(now, Pos);
			Flag = true;
		}
	}
	if (Flag)return;
	now = List.Bgn;
	node_ *tmp = new node_;
	Init_List(tmp);
	tmp->num = xx;
	Add(tmp, Pos);
	for (int i = maxlev - 1;i >= 0;--i)
	{
		while (xx >= now->Nxt[i]->num)now = now->Nxt[i];
		if(i<=k)
		{
			tmp->Nxt[i] = now->Nxt[i];
			now->Nxt[i] = tmp;
		}
	}
}
bool Search(node_ *Mm)
{
	node *now = Mm->Lst.bgn;
	for (int i = maxlev - 1;i >= 0;--i)
	{
		while (xx >= now->Nxt[i]->x)now = now->Nxt[i];
		if (now->x == xx)return true;
	}
	if (now->Nxt[0]->x <= yy)return true;
	return false;
}
bool Search(puu xx)
{
	node_ *now = List.Bgn;
	for (int i = maxlev - 1;i >= 0;--i)
	{
		while (xx >= now->Nxt[i]->num)now = now->Nxt[i];
		if (now->num == xx)
		{
			return Search(now);
		}
	}
	return false;
}

int main()
{
	srand(598562895);
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1;i <= n;++i)scanf("%d", a + i);
	for (int i = 1;i <= k-1;++i)
	{
		x.X = x.X*mul + a[i];
		//x.Y = (x.Y*mul + a[i]) % Mod;
		cc = cc* mul;
		//cc1 = cc1*mul%Mod;
	}
	Init_List();
	for (int i = k;i <= n;++i)
	{
		x.X = (x.X - cc*a[i - k]) * mul + a[i];
		//x.Y = ((x.Y + Mod - cc1*a[i - k] % Mod) * 10 + a[i]) % Mod;
		x.Y = 0;
		Add(x, i - k + 1);
#ifdef _DEBUG
		printf("%llu,%llu\n", x.X, x.Y);
#endif
	}
	int tmp;
	puu To;
	for (int i = 1;i <= m;++i)
	{
		scanf("%d%d", &xx, &yy); yy -= k - 1;
		To = mp(0, 0);
		for (int j = 1;j <= k;++j)
		{
			scanf("%d", &tmp);
			To.X = To.X*mul + tmp;
			//To.Y = (To.Y*mul + tmp) % Mod;
			To.Y = 0;
		}
		if (Search(To))puts("No");else puts("Yes");
	}
#ifdef _DEBUG
	system("pause");
#endif
	return 0;
}