「CF452F」Permutation

发表于 | 分类于 | | 浏览量： 次

等差数列？再见！

传送门

洛谷

CF452F

题解

对于一个三元组$A_i,A_j,A_k(i<j<k)$，如果它们构成等差数列，当且仅当有$A_k-A_j=A_j-A_i$。

考虑枚举中间的$j$，如果再枚举一个数$x$，如果$x$与$A_$存在并且在原排列中$A_j$的不同侧，那么就构成了一个等差的子序列。

所以可以再维护一个01序列，第$i$位上为0表示数字$i$在原序列中的位置小于$j$，否则大于$j$。

如果原序列中不存在三元等差数列，那么这个01序列应该是以$A_j$为中心左右对称的（可能有一端会多出来一截，忽略即可）。

每次$j$变化时，01序列上只有一个位置发生了变化，线段树维护一个正反的哈希值即可。

代码

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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300005,TT=1000000007;
int n,Pow[maxn];bool ans;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct SegmentTree
{
	struct Node{int Hash1,Hash2,len;}Tree[maxn*4];
	inline Node Merge(const Node& a,const Node& b){return (Node){(int)((LL)a.Hash1*Pow[b.len]%TT+b.Hash1)%TT,(int)((LL)b.Hash2*Pow[a.len]%TT+a.Hash2)%TT,a.len+b.len};}
	inline void PushUp(int rt){Tree[rt]=Merge(Tree[rt*2],Tree[rt*2+1]);}
	void Build(int L=1,int R=n,int rt=1)
	{
		if(L==R){Tree[rt].len=1;return;}
		int M=(L+R)>>1;
		Build(L,M,rt*2);
		Build(M+1,R,rt*2+1);
		PushUp(rt);
	}
	void UpdatePoint(int P,int L=1,int R=n,int rt=1)
	{
		if(L==R){Tree[rt].Hash1=Tree[rt].Hash2=1;return;}
		int M=(L+R)>>1;
		if(P<=M) UpdatePoint(P,L,M,rt*2);
		if(M<P) UpdatePoint(P,M+1,R,rt*2+1);
		PushUp(rt);
	}
	Node RangeQuery(int LL,int RR,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR) return Tree[rt];
		int M=(L+R)>>1;Node ret=(Node){0,0,0};
		if(LL<=M) ret=RangeQuery(LL,RR,L,M,rt*2);
		if(M<RR) ret=Merge(ret,RangeQuery(LL,RR,M+1,R,rt*2+1));
		return ret;
	}
}ST;
int main()
{
	n=read();Pow[0]=1;
	for(int i=1;i<=n;i++) Pow[i]=Pow[i-1]*2%TT;
	ST.Build();
	for(int i=1;i<=n;i++)
	{
		int Pi=read(),len=min(n-Pi+1,Pi);
		ST.UpdatePoint(Pi);
		if(ST.RangeQuery(Pi-len+1,Pi).Hash1!=ST.RangeQuery(Pi,Pi+len-1).Hash2){ans=true;break;}
	}
	printf("%s\n",ans?"YES":"NO");
	return 0;
}