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

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

题目大意

给定一个$1$到$n$的序列$a_i$，询问是否存在

$$1\le p_1<p_2<p_3<?<p_{len}\le n(len\ge 3)$$

使得$a_{p_1},a_{p_2},a_{p_3},\dots ,a_{p_{len}}$是一个等差序列。

有$T$组数据。

对于前$5$个数据测试点，$1\le n\le 5\times 10^5,T\le 5$，时限为$5s$

对于后$20$个数据测试点，$1\le n\le 10000,T\le 7$，时限为$2s$

题解

题意可以简化为判断这个序列是否存在一个长度为$3$的等差序列。

我们考虑在什么情况下会存在一个长度为$3$的等差序列。如果存在一个$a_i$，使得$a_i?k$和$a_i+k$在$a_i$的异侧，那么这三个数就构成等差序列。

那么我们可以按$i$从小到大来枚举$a_i$。因为$a_i$是一个$1$到$n$的排列，所以我们可以用一个数组$z$来维护$a_i$的值。在遍历$a_i$的时候，在数组$z$上将$a_i$左侧的点标为$1$，右侧的点标为$0$。

那么，如果不存在$k$使得$a_i?k$和$a_i+k$在$a_i$的异侧，那么$a_i?k$和$a_i+k$的$z$值就是相同的。我们将$z$以$a_i$为中心对折，如果对于所有重合部分，重合的两个数都相等，那么就说明不存在$k$使得$a_i?k$和$a_i+k$在$a_i$的异侧；否则，就存在一个长度为$3$的等差序列。

那我们怎么判断重合的两个数是否都相等呢？我们发现这其实就等价于重合部分左半边和右半边对称，也就是这一段是回文的。那我们只需要维护$z$数组的正序和倒序的哈希值，判断对应段的在两部分的哈希值是否相等。如果相等就说明不存在以$a_i$为中心的长度为$3$的等差序列，否则就说明存在以$a_i$为中心的长度为$3$的等差序列。

$z$数组的正序和倒序的哈希值可以用线段树来维护。

时间复杂度为$O(n\log n)$。

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int N=500000;
const long long mod=1e9+7;
int T,n,fl,a[N+5];
long long mi[N+5];
struct tree{
	long long ly[5*N+5];
	void build(int k,int l,int r){
		ly[k]=0;
		if(l==r) return;
		int mid=l+r>>1;
		build(lc,l,mid);
		build(rc,mid+1,r);
	}
	void down(int k,int l,int r){
		int mid=l+r>>1;
		ly[lc]=(ly[lc]+ly[k])%mod;
		ly[rc]=(ly[rc]+ly[k]*mi[mid+1-l])%mod;
		ly[k]=0;
	}
	void ch(int k,int l,int r,int x,int y){
		if(l>=x&&r<=y){
			ly[k]=(ly[k]+mi[l-x])%mod;
			return;
		}
		if(ly[k]) down(k,l,r);
		int mid=l+r>>1;
		if(x<=mid) ch(lc,l,mid,x,y);
		if(y>mid) ch(rc,mid+1,r,x,y);
	}
	long long find(int k,int l,int r,int x){
		if(!x) return 0;
		if(l==r&&l==x) return ly[k];
		if(ly[k]) down(k,l,r);
		int mid=l+r>>1;
		if(x<=mid) return find(lc,l,mid,x);
		else return find(rc,mid+1,r,x);
	}
	long long gt(int l,int r){
		return (find(1,1,n,r)-find(1,1,n,l-1)*mi[r-l+1]%mod+mod)%mod;
	}
}T1,T2;
int main()
{
	mi[0]=1;
	for(int i=1;i<=N;i++) mi[i]=mi[i-1]*2%mod;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		T1.build(1,1,n);
		T2.build(1,1,n);
		fl=0;
		for(int i=2;i<=n;i++){
			T1.ch(1,1,n,a[i-1],n);
			T2.ch(1,1,n,n-a[i-1]+1,n);
			int tmp=min(a[i]-1,n-a[i]);
			int l=a[i]-tmp,r=a[i]+tmp;
			if(T1.gt(l,r)!=T2.gt(n-r+1,n-l+1)){
				fl=1;break;
			}
		}
		if(fl) printf("Y\n");
		else printf("N\n");
	}
	return 0;
}