8
8
2016
0

BZOJ 3207:花神的嘲讽计划Ⅰ

Description

背景
花神是神,一大癖好就是嘲讽大J,举例如下:
“哎你傻不傻的!【hqz:大笨J】”
“这道题又被J屎过了!!”
“J这程序怎么跑这么快!J要逆袭了!”
……
描述
这一天DJ在给吾等众蒟蒻讲题,花神在一边做题无聊,就跑到了一边跟吾等众蒟蒻一起听。以下是部分摘录:
1.
“J你在讲什么!”
“我在讲XXX!”
“哎你傻不傻的!这么麻烦,直接XXX再XXX就好了!”
“……”
2.
“J你XXX讲过了没?”
“……”
“那个都不讲你就讲这个了?哎你傻不傻的!”
“……”
DJ对这种情景表示非常无语,每每出现这种情况,DJ都是非常尴尬的。
经过众蒟蒻研究,DJ在讲课之前会有一个长度为N方案,我们可以把它看作一个数列;
同样,花神在听课之前也会有一个嘲讽方案,有M个,每次会在x到y的这段时间开始嘲讽,为了减少题目难度,每次嘲讽方案的长度是一定的,为K。
花神嘲讽DJ让DJ尴尬需要的条件:
在x~y的时间内DJ没有讲到花神的嘲讽方案,即J的讲课方案中的x~y没有花神的嘲讽方案【这样花神会嘲讽J不会所以不讲】。
经过众蒟蒻努力,在一次讲课之前得到了花神嘲讽的各次方案,DJ得知了这个消息以后欣喜不已,DJ想知道花神的每次嘲讽是否会让DJ尴尬【说不出话来】。
 

Input

第1行3个数N,M,K;
第2行N个数,意义如上;
第3行到第3+M-1行,每行K+2个数,前两个数为x,y,然后K个数,意义如上;

Output

对于每一个嘲讽做出一个回答会尴尬输出‘Yes’,否则输出‘No’

Sample Input

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

Sample Output

No
Yes
Yes
Yes
No

HINT

 

题中所有数据不超过2*10^9;保证方案序列的每个数字<=N

2~5中有2 3 4的方案,输出No,表示DJ不会尴尬

1~8中没有3 2 1的方案,输出Yes,表示DJ会尴尬

5~7中没有4 5 6的方案,输出Yes,表示DJ会尴尬

2~5中没有1 2 3的方案,输出Yes,表示DJ会尴尬

1~7中有3 4 5的方案,输出No,表示DJ不会尴尬

 

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;
}
Category: 程序 | Tags: hash bzoj 跳表 | Read Count: 345

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com