P2757 [国家集训队]等差子序列

题目传送门

推荐一篇好题解

此题要求我们在一个序列中找出一个等差子序列。

显然，我们只需要考虑子序列长度len=3的情况，因为在长度为4的子序列中必定有一个长度为3的子序列。

问题就变成了：在序列找到三个数，满足a[j]-a[i]=a[k]-a[j]且i<j<k

移项，a[i]+a[k]=2 × a[j]

O(\(n^2\))的做法肯定是十分好想的。

枚举j和a[i]，查看vis[a[k]]是否为true即可。

这时观察数据，发现a[i]∈[1,n]，所以这时我们想到用hash来记录a[i]是否在之前出现过。

并且用线段树动态维护hash值(听说可以用树状数组，但是没写出来)

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=200005;

ll read(){

	ll x=0;char c=getchar();

	while(c<'0'||c>'9')c=getchar();

	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();

	return x;

}

const ll mo=19280817;

ll hash1[N<<2],hash2[N<<2];

ll n,pw[N];

void up(ll root,ll l,ll r,ll x){

	if(l==r&&l==x){hash1[root]=hash2[root]=1;return;}

	if(l>x||r<x)return;

	ll mid=l+r>>1;

	up(root<<1,l,mid,x);

	up(root<<1|1,mid+1,r,x);

	hash1[root]=(hash1[root<<1]*pw[r-mid]%mo+hash1[root<<1|1])%mo;

	hash2[root]=(hash2[root<<1]%mo+hash2[root<<1|1]*pw[mid-l+1])%mo;

}

ll Q1(ll root,ll l,ll r,ll beg,ll end){

	if(l>end||r<beg)return 0;

	if(l>=beg&&r<=end)return hash1[root];

	ll mid=l+r>>1,ans=0;

	if(mid<beg)return Q1(root<<1|1,mid+1,r,beg,end);

	if(mid+1>end)return Q1(root<<1,l,mid,beg,end);

	ans=Q1(root<<1,l,mid,beg,end)*pw[min(end,r)-mid]%mo;

	ans=(ans+Q1(root<<1|1,mid+1,r,beg,end))%mo;

	return ans;

}

ll Q2(ll root,ll l,ll r,ll beg,ll end){

	if(l>end||r<beg)return 0;

	if(l>=beg&&r<=end)return hash2[root];

	ll mid=l+r>>1,ans=0;

	if(mid<beg)return Q2(root<<1|1,mid+1,r,beg,end);

	if(mid+1>end)return Q2(root<<1,l,mid,beg,end);

	ans=Q2(root<<1|1,mid+1,r,beg,end)*pw[mid-max(beg,l)+1]%mo;

	ans=(ans+Q2(root<<1,l,mid,beg,end))%mo;

	return ans;

}

int main(){

	int T=read();pw[0]=1;for(ll i=1;i<=10000;++i)pw[i]=(pw[i-1]*2)%mo;

	while(T--){

		memset(hash1,0,sizeof(hash1));

		memset(hash2,0,sizeof(hash2));

		n=read();bool flag=1;

		for(ll i=1;i<=n;++i){

			ll x=read();

			if(!flag)continue;

			ll len=min(x-1,n-x);

			if((Q1(1,1,n,x-len,x-1)+mo)%mo!=(Q2(1,1,n,x+1,x+len)+mo)%mo){flag=0;continue;}

			up(1,1,n,x);

		}

		if(flag)puts("N");else puts("Y");

	}

	return 0;

}

巴特西

P2757 [国家集训队]等差子序列

P2757 [国家集训队]等差子序列

最新文章

热门文章