因为只要求存在性,故而观察到长度>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;
}