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

因为只要求存在性，故而观察到长度>3的等差序列只需要求前3项即可。
于是就转化为求 $$ a_j+a_k=2*a_i $$ 是否存在。
观察到数据范围 n<=10000 ，于是用两个 bitset 分别维护前缀桶和后缀桶，稍微左右移一下求交即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
/*

*/
const int N=10005;
bitset<N> pre,lst;
int n,a[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	pre.reset();lst.reset();
	for(int i=2;i<=n;++i){
		lst[n-a[i]]=1;
	}
	for(int i=2;i<n;++i){
		pre[a[i-1]]=1;lst[n-a[i]]=0;
		if(((2*a[i]>=n?lst<<(2*a[i]-n):lst>>(n-2*a[i]))&pre).any()){
			puts("Y");
			return;
		}
	}
	puts("N");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}