Tang-Dreamoon's Blog

bzoj 2124 等差子序列

发表于 | 分类于 ， ，

哈希 + 树状数组

　　题目链接：bzoj 2124

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：既然这个等差子序列只有三个，而且这是一个从 1 到 N 的排列的话， 我们可以从左到右枚举一下中间那个数 X ，如果存在等差子序列的话，以 X 为中心对称的两个点一定一个已经出现过而另一个还没有出现过。所以我们可以用一个零一权值串来表示这个数有没有出现过，如果以 X 为中心两个对称的半径相等的零一串有一位不同，即异或起来不为零，那么就是找到了一个等差子序列。如何比较两个串呢？使用我们伟大的哈希啊！

　　我思故我在：显然这个题不可能暴力的计算哈希值，所以我们肯定得用一种数据结构维护一下哈希值，这道题我用的是树状数组，我们当然还可以用线段树啦！不过只要一做就会发现一个问题：那就是左右这两个串“方向”是相反的，所以我们需要维护正反两个树状数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
long long  modd=1000000009ll;
long long  shu[10100];
long long  zzu[10100];
long long  tot[10100];
int n;
void mak()
{
	tot[1]=1;
	for(int i=2;i<=10001;i++)
	{
		tot[i]=tot[i-1]*2%modd;
	}
}
void add1(int x)
{
	for(int i=x;i<=n;i=i+(i&-i))
	{
		shu[i]=(shu[i]+tot[i-x+1])%modd;
	}
}
void add2(int x)
{
	for(int i=x;i>=1;i=i-(i&-i))
	{
		zzu[i]=(zzu[i]+tot[x-i+1])%modd;
	}
}
long long  ask1(int x)
{
	long long  ans=0;
	for(int i=x;i>=1;i=i-(i&-i))
	{
		ans=(ans+shu[i]*tot[x-i+1]%modd)%modd;
	}
	return ans;
}
long long  ask2(int x)
{
	long long  ans=0;
	for(int i=x;i<=n;i=i+(i&-i))
	{
		ans=(ans+zzu[i]*tot[i-x+1]%modd)%modd;
	}
	return ans;
}
int main()
{
	mak();
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			int lena=min(x-1,n-x);
			if(lena==0){add1(x),add2(x);continue;}
			long long  first=(ask1(x-1)-ask1(x-lena-1)*tot[lena+1]%modd+modd)%modd;
			long long  secon=(ask2(x+1)-ask2(x+lena+1)*tot[lena+1]%modd+modd)%modd;
		//	cout<<x<<" "<<first<<" "<<secon<<endl;
			if((first^secon)!=0)
			{
			//	cout<<x<<endl;
				puts("Y");
				for(int j=i+1;j<=n;j++)
				{
					scanf("%d",&x);
				}
				goto Ed;
			}
			add1(x),add2(x);
		}
		puts("N");
		Ed:
		memset(shu,0,sizeof(shu));
		memset(zzu,0,sizeof(zzu));
	}
	return 0;
}