LOJ 6287 诗歌 题解

LOJ 6287 诗歌 题解

xiaoh 2020-9-8

题意

给定$1-n$的排列$p_i$。若$\exist 1\leq i<j<k\leq n$，且$p_i-p_j=p_j-p_k$，输出YES，否则输出NO

数据范围

$1\leq n\leq 3\times 10^5$

题解

毒瘤联测题

首先，考虑使用$hash$。顺序扫描整个序列，当$i$出现在当前位置$pos$的左边时，$h_i=1$，否则$h_i=0$。则对于当前值$p_{pos}$，对于任意的$p_{pos-d}$和$p_{pos+d}$必须相等，否则取这一对即可满足条件。用正序和倒序两个树状数组维护$hash$函数，然后每个位置查询左侧和右侧是否回文即可。复杂度$O(n\log n)$。

Code

#include<bits/stdc++.h>

using namespace std;

const int PP=13331;
const int MO=998244353;
const int maxN=300000+5;

int a[maxN];
long long P[maxN];
struct SegTree
{
	long long d;
}t1[maxN<<2],t2[maxN<<2];
int n,res1,res2;

void pushup1(int u,int l,int r)
{
	int m=(l+r)>>1;
	t1[u].d=(t1[u<<1].d*P[r-m]%MO+t1[u<<1|1].d)%MO;
}
void pushup2(int u,int l,int r)
{
	int m=(l+r)>>1;
	t2[u].d=(t2[u<<1|1].d*P[m-l+1]%MO+t2[u<<1].d)%MO;
}

void build2(int u,int l,int r)
{
	if (l==r)
	{
		t2[u].d=1; return;
	}
	int m=(l+r)>>1;
	build2(u<<1|1,m+1,r); build2(u<<1,l,m);
	pushup2(u,l,r);
}

void update1(int u,int l,int r,int x)
{
	if (l==r)
	{
		t1[u].d=1; return;
	}
	int m=(l+r)>>1;
	if (x<=m) update1(u<<1,l,m,x);
	else update1(u<<1|1,m+1,r,x);
	pushup1(u,l,r);
}
void update2(int u,int l,int r,int x)
{
	if (l==r)
	{
		t2[u].d=1; return;
	}
	int m=(l+r)>>1;
	if (x>m) update2(u<<1|1,m+1,r,x);
	else update2(u<<1,l,m,x);
	pushup2(u,l,r);
}

void query1(int u,int l,int r,int ql,int qr)
{
	if (ql<=l && r<=qr)
	{
		res1=(res1+t1[u].d*P[qr-r]%MO)%MO;
		return;
	}
	int m=(l+r)>>1;
	if (ql<=m) query1(u<<1,l,m,ql,qr);
	if (qr>m) query1(u<<1|1,m+1,r,ql,qr);
}
void query2(int u,int l,int r,int ql,int qr)
{
	if (ql<=l && r<=qr)
	{
		res2=(res2+t2[u].d*P[l-ql]%MO)%MO;
		return;
	}
	int m=(l+r)>>1;
	if (qr>m) query2(u<<1|1,m+1,r,ql,qr);
	if (ql<=m) query2(u<<1,l,m,ql,qr);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	P[0]=1;
	for (int i=1;i<=n;++i) P[i]=P[i-1]*PP%MO;
	//build2(1,1,n);
	bool flag=0;
	for (int i=1;i<=n;++i)
	{
		int len=min(a[i]-1,n-a[i]);
		//printf("%d %d\n",i,len);
		if (len>=1)
		{
			res1=0; query1(1,1,n,a[i]-len,a[i]-1);
			res2=0; query2(1,1,n,a[i]+1,a[i]+len);
			//printf("%d %d\n",res1,res2);
			if (res1!=res2) { flag=1; break; }
		}
		update1(1,1,n,a[i]); update2(1,1,n,a[i]);
	}
	if (flag) printf("YES\n");
	else printf("NO\n");
	return 0;
}