CF452F等差子序列 & 线段树+hash查询区间是否为回文串

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

记录一下一个新学的线段树基础trick(真就小学生trick呗)

给你一个1到n的排列，你需要判断该排列内部是否存在一个3个元素的子序列(可以不连续)，使得这个子序列是等差序列。\(n\) <=3e5

考虑等差数列的相关性质，对于一个3个数的等差数列，当 \(a_i\) 作为中间项可行时，当且仅当一定存在至少1个 \(k\)，使得 \(a_i-k\) 这个元素在它的左边，\(a_i+k\) 这个元素在它的右边（为了方便，这里的 \(k\)可以是负数）

那我们在顺序枚举 \(a_i\) 的过程中，不妨把用过的 \(a_i\) 标记成1，没用过的标记成零，然后对于所有范围内的 \(k\) 暴力判一遍

于是你就得到了一个 \(n^2\) 的暴力

大概长这样

//Talking to the moon

#include <bits/stdc++.h>

#define N 1000010

#define M 2000010

#define int long long

#define int_edge int to[M],val[M],nxt[M],head[N],cnt=0;

using namespace std;

int used[10010],a[10010];

//void add_edge(int x,int y ){to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;}

int read(){

	int fu=1,ret=0;char ch;

	for(;!isdigit(ch);ch=getchar())if(ch=='-')fu*=-1;

	for(;isdigit(ch);ch=getchar())ret=(ret<<1)+(ret<<3)+ch-'0';

	return ret*fu;

}

signed main()

{

	int n=read(),ans=0;

	for(int i=1;i<=n;i++)a[i]=read();

	for(int i=1;i<=n;i++)

	{

		for(int j=1;a[i]-j>=1&&a[i]+j<=n;j++)

			if(used[a[i]-j]!=used[a[i]+j]){ans=1;break;}

		if(ans==1)break;

		used[a[i]]=1;

	}

	if(ans==1)puts("YES");

		else puts("NO");

	return 0;

}

接下来是正解部分

我们发现正向考虑枚举 \(k\) 好像没有什么优化空间，而且题目也没让我们找 \(k\) ，那么正难则反，我们可以考虑作为中间项不可行的情况，即不存在 \(k\) 使得 \(a_i+k\) 和 \(a_i-k\) 的标记相同

那不就是 回文串 吗

于是我们的问题就变成了在值域上搞单点修改加区间判断是否回文

先不考虑修改，判断回文串其实是有一个非常优秀的朴素 Hash 算法的

就是考虑正反向各 Hash 一遍，然后判断查询区间的正反 Hash 值是否相等即可

然后 Hash 值是可以加减的

也就是说你把 a 在第1位的 hash 值加上 b 在第2位的 hash 值加起来就可以得到 ab 的 hash 值

那么修改就简单了，我们可以把这个 Hash 移到一棵线段树上（树状数组也可）

每个叶子节点存的是单点 hash 后的值

然后就可以支持单点修改，区间查询了

需要注意的是合并的时候需要把每一位乘上这一位对应的 hash 底数（比如131的多少次方什么的）

查询的时候也是

//Talking to the moon

#include <bits/stdc++.h>

#define N 300010

#define M 2000010

#define int unsigned long long

#define int_edge int to[M],val[M],nxt[M],head[N],cnt=0;

using namespace std;

int a[N],h[N];

//void add_edge(int x,int y ){to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;}

int read(){

	int fu=1,ret=0;char ch;

	for(;!isdigit(ch);ch=getchar())if(ch=='-')fu*=-1;

	for(;isdigit(ch);ch=getchar())ret=(ret<<1)+(ret<<3)+ch-'0';

	return ret*fu;

}

int ls(int x){return x*2;}

int rs(int x){return x*2+1;}

struct Seg1{

	int tr[N*4];

	void update(int nw,int l,int r,int x){

		if(l==r){

			tr[nw]++;

			return;

		}

		int mid=(l+r)/2;

		if(x<=mid)update(ls(nw),l,mid,x);

			else update(rs(nw),mid+1,r,x);

		tr[nw]=tr[ls(nw)]*h[r-mid]+tr[rs(nw)];

	}

	int query(int nw,int l,int r,int x,int y){

		if(x<=l&&r<=y){

			return tr[nw]*h[y-r];

		}

		int mid=(l+r)/2,sum=0;

		if(x<=mid)sum+=query(ls(nw),l,mid,x,y);

		if(y>mid)sum+=query(rs(nw),mid+1,r,x,y);

		return sum;

	}

}S1;

struct Seg2{

	int tr[N*4];

	void update(int nw,int l,int r,int x){

		if(l==r){

			tr[nw]++;

			return;

		}

		int mid=(l+r)/2;

		if(x<=mid)update(ls(nw),l,mid,x);

			else update(rs(nw),mid+1,r,x);

		tr[nw]=tr[rs(nw)]*h[mid-l+1]+tr[ls(nw)];

	}

	int query(int nw,int l,int r,int x,int y){

		if(x<=l&&r<=y){

			return tr[nw]*h[l-x];

		}

		int mid=(l+r)/2,sum=0;

		if(x<=mid)sum+=query(ls(nw),l,mid,x,y);

		if(y>mid)sum+=query(rs(nw),mid+1,r,x,y);

		return sum;

	}

}S2;

signed main()

{

	int n=read(),ans=0;

	h[0]=1;for(int i=1;i<=n;i++)h[i]=h[i-1]*131;

	for(int i=1;i<=n;i++)

	{

		a[i]=read();

		int num=min(a[i]-1,n-a[i]),l=a[i]-num,r=a[i]+num;

		if(S1.query(1,1,n,l,r)!=S2.query(1,1,n,l,r)){ans=1;break;}

		S1.update(1,1,n,a[i]);S2.update(1,1,n,a[i]);

	}

	if(ans)puts("YES");

		else puts("NO");

	return 0;

}