bzoj 2124 线段树维护hash值

2124: 等差子序列

Time Limit: 3 Sec Memory Limit: 259 MB
Submit: 2777 Solved: 977
[Submit][Status][Discuss]

Description
给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3)，
使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

Input
输入的第一行包含一个整数T，表示组数。
下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。
N<=10000，T<=7

Output
对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。

Sample Input
2

3

1 3 2

3

3 2 1
Sample Output
N

Y

这道题，直观地，我们可以发现，长度大于等于3的子序列，实际上我们只需要找长度为3的等差子序列就可以了，因为长度大于3的等差子序列，必然可以分解为长度为3的子序列。

然后还有重要的一点就是，这是一个排列。所以每个数字只出现一次。

然后我们考虑枚举每一个数字 j ，看是否存在 i<j<k && i+k=j*2 即可。然后需要看的数字特别多，我们不能一个一个枚举，必然TLE。 我们必须快速枚举 所有数字，我们可以发现，对于一个表示数字是否出现过的0/1串，只有当他们相等时，代表数字都在这个数字之前出现了，或者都在这个数字之后出现。

相当于，我们就是按照数字枚举，把出现过的放到权值线段树中，然后对于每一对数字，要么都出现，要么都未出现，这就是不行的。否则可以。

于是我们可以用线段树维护hash值，然后直接看hash值是否相等，就能知道这段序列是否相等了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10,mod=1e9+7;//hash
int T,n,a[N],flag,base[N];
struct node{int l,r,h1,h2;}t[N<<2];
inline void push_up(int p){
	int l1=t[p<<1].r-t[p<<1].l+1;
	int l2=t[p<<1|1].r-t[p<<1|1].l+1;
	t[p].h1=(t[p<<1].h1+t[p<<1|1].h1*base[l1]%mod)%mod;
	t[p].h2=(t[p<<1].h2*base[l2]%mod+t[p<<1|1].h2)%mod;
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r; t[p].h1=t[p].h2=0;
	if(l==r)	return ;	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
}
void change(int p,int x){
	if(t[p].l==t[p].r)	return void(t[p].h1=t[p].h2=1);
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	change(p<<1,x);	
	else	change(p<<1|1,x);
	push_up(p);
}
int ask1(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].h1;
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask1(p<<1,l,r);
	else if(l>mid)	return ask1(p<<1|1,l,r);
	else	return (ask1(p<<1,l,mid)+ask1(p<<1|1,mid+1,r)*base[mid-l+1]%mod)%mod;
}
int ask2(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].h2;
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask2(p<<1,l,r);
	else if(l>mid)	return ask2(p<<1|1,l,r);
	else	return (ask2(p<<1,l,mid)*base[r-mid]%mod+ask2(p<<1|1,mid+1,r))%mod;
}
signed main(){
	scanf("%lld",&T); base[0]=1;
	for(int i=1;i<=10000;i++)	base[i]=base[i-1]*13331%mod; 
	while(T--){
		scanf("%lld",&n); flag=0; build(1,1,n);
		for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
		for(int i=1;i<=n&&!flag;i++){
			int len=min(a[i]-1,n-a[i]);
			if(a[i]!=1&&a[i]!=n&&ask1(1,a[i]-len,a[i]-1)!=ask2(1,a[i]+1,a[i]+len))	
				flag++;
			change(1,a[i]); 
		}
		puts(flag?"Y":"N");
	}
	return 0;
}