P2757 [国家集训队]等差子序列

双倍经验：CF452F Permutation

线段树+哈希

我菜死了调了好久然后搞了半天才 AC， 所以在代码中会提到一些坑点

分析

显然的，只要找到三元等差数列即可，因为

• 题目要求 $len\geq3$，所以只用满足最低条件
• 更多元的都是在三元的基础上的 三生万物（

对于三元等差数列，有一个常见技巧就是枚举中值 $b=a_i$，然后找 $b-k,b+k$ 是否在同侧，如果在同侧就寄了，不在就赢了

如果暴力枚举 $b,k$ 那就是平方级别了，妥妥 TLE

考虑优化，对于枚举 $b$，无法优化，只能考虑优化 $k$ 的寻找

动态维护存在性 01 串，表示每一个数是否在左边出现，在右边是否出现，如果是回文串，那就寄了，因为一大一小全部集中在左侧或右侧，否则就赢了

如何快速判断回文？字符串哈希，如果正着的哈希等于反着的哈希，那么就回文

那么就是搞一个 $\log$ 级的动态维护哈希值的数据结构，考虑使用线段树，每个节点记录长度和正反哈希值

没了，思路就这么简单

代码

如果没有深入理解的话坑点会比较多，所以结合注释食用

#include <bits/stdc++.h>
#define ll unsigned long long
#define inl inline
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define pre(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
using namespace std;
const int N=5e5+10,mod=1e9+7,B=27;
struct Node{
	ll h1,h2;int l1,l2;
	Node(const ll v=0,const int l=0){h1=h2=v;l1=l2=1;}
}t[N<<2];//这里用了一个大结构体，h1,h2 是正反哈希值，l1,l2表示长度
int n,a[N],T;
ll p[N];
bool flag;
Node comp(Node x,Node y){
	Node tmp;
	tmp.h1=(x.h1*p[y.l1]%mod+y.h1)%mod;
	tmp.h2=(y.h2*p[x.l2]%mod+x.h2)%mod;//请注意 h2 表示反哈希，所以要相对于正哈希反着操作，要不然就 WA 16 pts
	tmp.l1=x.l1+y.l1;tmp.l2=x.l2+y.l2;
	return tmp;
}//合并操作，用于上传
namespace Tree{
	#define ls k<<1
	#define rs k<<1|1
	#define mid (l+r>>1)
	#define pushup(k) t[k]=comp(t[ls],t[rs])
	inl void update(int k,int l,int r,int x){
		if(x<l||x>r)return ;
		if(l==r){
			Node tmp;tmp.h1=tmp.h2=1;tmp.l1=tmp.l2=1;
			t[k]=tmp;
			return ;
		}
		update(ls,l,mid,x);update(rs,mid+1,r,x);pushup(k);
	}
	inl void build(int k,int l,int r){
		if(l==r){
			Node tmp;tmp.h1=tmp.h2=0;tmp.l1=tmp.l2=1;
			t[k]=tmp;
			return ;
		}
		build(ls,l,mid);build(rs,mid+1,r);pushup(k);
	}
	Node query(int k,int l,int r,int x,int y){
		if(x<=l&&y>=r)return t[k];
		if(y<=mid)return query(ls,l,mid,x,y);
		if(mid<x)return query(rs,mid+1,r,x,y);
		return comp(query(ls,l,mid,x,mid),query(rs,mid+1,r,mid+1,y));
	}
}
using namespace Tree;
signed main(void){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--){
		// rep(i,1,N<<2)t[i].h1=t[i].h2=t[i].l1=t[i].l2=0;
		p[0]=1;flag=0;
		cin>>n;
		rep(i,1,n)p[i]=p[i-1]*B%mod;
		build(1,1,n);
		rep(i,1,n){
			int x;cin>>x;//不论是否找到了三元等差数列，都要读完（一上来因为这个寄了一发）
			if(flag)continue;
			update(1,1,n,x);
			int len=min(x-1,n-x);
			if(len<=0)continue;//不合法特判
			if(query(1,1,n,x-len,x-1).h1!=query(1,1,n,x+1,x+len).h2){//如果正哈希不等于反哈希，找到了
				cout<<"Y\n";flag=1;
			}
		}
		if(!flag)cout<<"N\n";
	}
}

完结撒花！