LOJ6287

题目链接

题意：

给出(n(n<=1e5))的一个排列{({p_i})}(_{i=1}^n)，判断是否存在一个三元组((i,j,k))使得(p_i-p_j==p_j-p_k)

题解：

绝妙的题目
考虑枚举中间点j
开一颗权值线段树维护数x在j左侧是否出现过
如果出现过记为1，反之为0
设len为(p_j)最长能延伸的长度(即(min(n-p_j,p_j-1)))
每次询问在线段树上查找以j为中心，len为半径(向左和向右)的一段哈希值(哈希的每一位就是如前所述的1/0)
如果二者相等，那么满足条件的两个数在同一侧，不可行
如此循环即可
至于如何快速求出hash，见代码(要维护两种哈希：正的和反的)

code:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,base=3,mod=19930219;
int n,a[N],pw[N];
int hash_z[N<<2],hash_f[N<<2];
inline int read()
{
	int s=0,w=1; char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
	for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
	return s*w;
}
inline void up(int rt,int l,int r)
{
	int mid=l+r>>1;
	hash_z[rt]=(1ll*hash_z[rt<<1]*pw[r-mid]%mod+hash_z[rt<<1|1])%mod;
	hash_f[rt]=(1ll*hash_f[rt<<1|1]*pw[mid-l+1]%mod+hash_f[rt<<1])%mod;
}
void update(int rt,int l,int r,int x)
{
	if(l==r){hash_z[rt]=hash_f[rt]=1;return;}
	int mid=l+r>>1;
	if(x<=mid)update(rt<<1,l,mid,x);
	else update(rt<<1|1,mid+1,r,x);
	up(rt,l,r);
}
int query(int rt,int l,int r,int x,int y,bool tp)
{
	if(l==x&&r==y)return tp?hash_f[rt]:hash_z[rt];
	int mid=l+r>>1;
	if(y<=mid)return query(rt<<1,l,mid,x,y,tp);
	else if(x>mid) return query(rt<<1|1,mid+1,r,x,y,tp);
	else
	{
		int L=query(rt<<1,l,mid,x,mid,tp),R=query(rt<<1|1,mid+1,r,mid+1,y,tp);
		if(!tp)return (1ll*L*pw[y-mid]%mod+R)%mod;
		else return (1ll*R*pw[mid-x+1]%mod+L)%mod;
	}
}
int main()
{
	n=read();pw[0]=1;
	for(int i=1;i<=n;++i)
		a[i]=read(),pw[i]=pw[i-1]*base%mod;
	update(1,1,n,a[1]);
	for(int i=2;i<n;++i)
	{
		update(1,1,n,a[i]);
		if(a[i]==1||a[i]==n)continue;
		int len=min(a[i]-1,n-a[i]);
		if(query(1,1,n,a[i]-len,a[i],0)!=query(1,1,n,a[i],a[i]+len,1))
		{
			puts("YES");
			return 0;
		}
	}
	puts("NO");
	return 0;
}