[JZOJ1913][BZOJ2124]等差子序列

description

给一个1到N的排列{Ai},询问是否存在1=p1p2p3p4p5…pLen=N (Len=3),
使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。


analysis
  • 找出一个长度为 3 3 3的等差序列即可满足要求,长度为 3 3 3的都没有,更长的序列也不存在

  • 暴力可以枚举每一个 a [ i ] a[i] a[i],然后枚举 x x x,判断 a [ i ] − x , a [ i ] + x a[i]-x,a[i]+x a[i]x,a[i]+x是否在 i i i位置前后,考虑优化这个 O ( n 2 ) O(n^2) O(n2)

  • 从前往后插入每一个数,设当前位的数字是 x x x,若当前位一定不是某等差序列的中间位,意味着与 x x x差相同的每一对数都出现过了

  • 如果在数的映射上,以 x x x为中心的 01 01 01串是回文串,则当前位为中间的等差序列不存在,否则就存在,这个比较好理解

  • 那么维护顺序、逆序的 01 01 01串哈希就用线段树,从而快速判断回文串,时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)


code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#includestdio.h
#includestring.h
#includealgorithm
#define MAXN 50005
#define p 805306457
#define ha 1610612741
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i=b;++i)
#define fd(i,a,b) for (reg i=a;i=b;--i)

using namespace std;

ll trl[MAXN],trr[MAXN];
ll a[MAXN],powp[MAXN];
ll n,T,flag;

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch'0' || '9'ch){if (ch=='-')f=-1;ch=getchar();}
	while ('0'=ch  ch='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline ll max(ll x,ll y){return xy?x:y;}
inline ll min(ll x,ll y){return xy?x:y;}
inline void modify(ll t,ll l,ll r,ll x)
{
	if (l==r){trl[t]=trr[t]=p;return;}ll mid=(l+r)1;
	x=mid?modify(t1,l,mid,x):modify((t1)+1,mid+1,r,x);

	trl[t]=(trl[t1]*powp[(r-l+1)1]%ha+trl[(t1)+1])%ha;
	trr[t]=(trr[t1]+trr[(t1)+1]*powp[r-l+1-((r-l+1)1)]%ha)%ha;
}
inline ll getl(ll t,ll l,ll r,ll x,ll y)
{
	if (xy)return 0;if (l==x  y==r)return trl[t];ll mid=(l+r)1;

	if (y=mid)return getl(t1,l,mid,x,y);else if (xmid)return getl((t1)+1,mid+1,r,x,y);
	else return (getl(t1,l,mid,x,mid)*powp[y-mid]%ha+getl((t1)+1,mid+1,r,mid+1,y))%ha;
}
inline ll getr(ll t,ll l,ll r,ll x,ll y)
{
	if (xy)return 0;if (l==x  y==r)return trr[t];ll mid=(l+r)1;

	if (y=mid)return getr(t1,l,mid,x,y);else if (xmid)return getr((t1)+1,mid+1,r,x,y);
	else return (getr(t1,l,mid,x,mid)+getr((t1)+1,mid+1,r,mid+1,y)*powp[mid-x+1]%ha)%ha;
}
int main()
{
	//freopen("T1.in","r",stdin);
	T=read(),powp[0]=1;
	fo(i,1,40000)powp[i]=powp[i-1]*p%ha;
	while (T--)
	{
		memset(trl,0,sizeof(trl));
		memset(trr,0,sizeof(trr)),flag=0;
		n=read();fo(i,1,n)a[i]=read();
		fo(i,1,n)
		{
			ll x=a[i],len=min(x-1,n-x);
			if (getl(1,1,n,x-len,x-1)!=getr(1,1,n,x+1,x+len)){flag=1;break;}
			modify(1,1,n,x);
		}
		printf(flag?"Y\n":"N\n");
	}
	return 0;
}
最新回复(0)
/jishusD08MqdV6gppK7vknADaOuBm2pIqQe2GDhLgFvvb17Q_3D4858321
8 简首页