CF452F Permutation

对于一个数 \(a_i\),如果其左侧存在一个数 \(a_j\),右侧存在一个数 \(a_k\),满足 \(a_j-a_i=a_i-a_k\),则说明 \((a_j,a_i,a_k)\) 是一个长度为 \(3\) 的等差数列子序列。

观察到 \(a_j\)\(a_k\)\(a_i\) 不同侧且差值相等。我们可以用一个较松的条件去约束前者,一个较紧的条件去约束后者。

从小到大枚举 \(i\),用 \(a\) 的权值线段树维护子段的哈希值,表示某个数是否在当前位置 \(i\) 的右侧。每次将 \(a_i\) 位置上的数置为 \(0\)

如果存在任意 \(a_i\) 为中心到较近边界(\(1\)\(n\))为一侧的串不是回文串,则答案为 YES

#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define Mod 1000000007
#define Base 2
#define Min(x,y)((x)<(y)?x:y)
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
#define ls(p)((p)<<1)
#define rs(p)((p)<<1|1)
struct Segment_Tree
{
	int hach[2],l,r;
}t[1200005];
int a[N],base[N];
int read()
{
	int A;
	bool K;
	char C;
	C=A=K=0;
	while(C<‘0‘||C>‘9‘)K|=C==‘-‘,C=getchar();
	while(C>‘/‘&&C<‘:‘)A=(A<<3)+(A<<1)+(C^48),C=getchar();
	return(K?-A:A);
}
inline void pushup(int p)
{
	t[p].hach[0]=(1LL*t[ls(p)].hach[0]*base[t[rs(p)].r-t[rs(p)].l+1]+t[rs(p)].hach[0]+Mod)%Mod;
	t[p].hach[1]=(1LL*t[rs(p)].hach[1]*base[t[ls(p)].r-t[ls(p)].l+1]+t[ls(p)].hach[1]+Mod)%Mod;
}
void build(int p,int l,int r)
{
	t[p].l=l;
	t[p].r=r;
	if(t[p].l==t[p].r)
	{
		t[p].hach[0]=t[p].hach[1]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid),build(rs(p),mid+1,r);
	pushup(p);
}
void change(int p,int x)
{
	if(t[p].l==t[p].r)
	{
		t[p].hach[0]=t[p].hach[1]=0;
		return;
	}
	change((t[ls(p)].r>=x?ls(p):rs(p)),x);
	pushup(p);
}
int ask(int p,int x,int y,bool z)
{
	if(x<=t[p].l&&t[p].r<=y)return t[p].hach[z];
	int ret=0;
	if(!z)
	{
		if(t[ls(p)].r>=x)ret=ask(ls(p),x,y,z);
		if(t[rs(p)].l<=y)ret=(1LL*ret*base[Min(y,t[rs(p)].r)-Max(t[ls(p)].r,x-1)]+ask(rs(p),x,y,z))%Mod;
	}
	else
	{
		if(t[rs(p)].l<=y)ret=ask(rs(p),x,y,z);
		if(t[ls(p)].r>=x)ret=(1LL*ret*base[Min(y,t[ls(p)].r)-Max(x,t[ls(p)].l)+1]+ask(ls(p),x,y,z))%Mod;
	}
	return ret;
}
int main()
{
	int n,i,len;
	n=read();
	base[0]=1;
	For(i,1,n)a[i]=read(),base[i]=base[i-1]*Base%Mod;
	build(1,1,n);
	For(i,1,n)
	{
		len=Min(a[i]-1,n-a[i])+1;
		if(ask(1,a[i]-len+1,a[i],0)!=ask(1,a[i],a[i]+len-1,1))puts("YES"),exit(0);
		change(1,a[i]);
	}
	puts("NO");
	return 0;
}
/*6
1 5 3 4 6 2*/

CF452F Permutation

上一篇:Vue3使用vant插件


下一篇:QString的操作总结