RT，本人用NTT + 分块判断是否存在等差子序列。

按理来说，时间复杂度是 O($m*n$ + $n/m * nlogn$)的，想着应该可以过的，但是却T了，于是我大胆的把NTT注释掉了后看到底是什么导致我超时，但是它过了！！！！！我直接大呼好家伙

敢问这数据到底是有多令人害怕.......

($m$ 是分块的大小)

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 50;
#define int long long
const int Mod = 998244353;
int A[MAXN];
int Lef[MAXN],Rig[MAXN];
int JL[MAXN],JR[MAXN];
int n;
int L[1005],R[1050],num = 0,rev[MAXN];
int pre[MAXN],nxt[MAXN];
int lim = 1, l = 0,m;
long long Ans = 0;

inline int read() {
	int x = 0 , flag = 1;
	char ch = getchar();
	for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
	for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	return x * flag;
}

int quickpower(int x,int y) {
	int ans = 1 , op = x;
	while(y) {
		if(y & 1) ans *= op , ans %= Mod;
		op *= op , op %= Mod;
		y >>= 1;
	}
	return ans;
}

void NTT(int * a , int type) {
	for(int i = 0 ; i < lim ; i ++)
		if(i < rev[i]) swap(a[i],a[rev[i]]);
	for(int mid = 1 ; mid < lim ; mid <<= 1) {
		int gn = quickpower(3 , (Mod - 1) / (mid << 1));
		for(int i = 0 ; i < lim ; i += (mid << 1)) {
			int g = 1;
			for(int j = 0 ; j < mid ; j ++ , g = (g * gn) % Mod) {
				int x = a[i + j] , y = a[i + j + mid] * g % Mod;
				a[i + j] = (x + y) % Mod;
				a[i + j + mid] = (x - y + Mod) % Mod;
			}
		}
	}
	if(type == 1) return ;
	reverse(a + 1, a + lim);
	int inv = quickpower(lim , Mod - 2);
	for(int i = 0 ; i < lim ; i ++) a[i] *= inv , a[i] %= Mod;
	return ;
}

void deal(int x) {
	for(int i = L[x] ; i <= R[x] ; i ++) Rig[A[i]] --;
	for(int i = L[x] ; i <= R[x] ; i ++) {
		for(int j = i + 1 ; j <= R[x] ; j ++) {
			if(A[j] < A[i] * 2) {
				Ans += pre[A[i] - (A[j] - A[i])];
				Ans += Lef[A[i] - (A[j] - A[i])];
			}
			if(A[j] * 2 > A[i])
			Ans += Rig[A[j] + (A[j] - A[i])];
		}
		pre[A[i]] ++;
	}
	for(int i = 0 ; i <= m ; i ++) JL[i] = Lef[i];
	for(int i = 0 ; i <= m ; i ++) JR[i] = Rig[i];
	for(int i = m + 1; i < lim ; i ++) JL[i] = JR[i] = 0;
	//NTT(JL , 1 ) ; NTT( JR , 1 );
	for(int i = 0 ; i < lim; i ++) JL[i] *= JR[i] , JL[i] %= Mod;
	//NTT( JL , - 1);
	for(int i = L[x] ; i <= R[x]; i ++) 
	Ans += JL[2 * A[i]], pre[A[i]] = 0,Lef[A[i]] ++;
	return ;
}

signed main() {
	
	int Q = read();
	while(Q --) {
		n = read();
		memset(JL,0,sizeof(JL)); memset(Rig,0,sizeof(Rig));
		memset(JR,0,sizeof(JR)); memset(Lef,0,sizeof(Lef)); 
		lim = 1 , l = 0;
		m = n; num = 0; Ans = 0;
		for(int i = 1 ; i <= n ; i ++) A[i] = read() , Rig[A[i]] ++;
		int block = 200;//块的大小
		while(R[num] != n) {
			num ++;
			L[num] = R[num - 1] + 1;
			R[num] = min(num * block , n);
		}
		for( ; lim <= m * 2 ; lim <<= 1) l ++;
		for(int i = 0 ; i <= lim ; i ++) 
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
		for(int i = 1 ; i <= num ; i ++) deal(i);
		if(Ans != 0)cout << "Y" << endl;
		else cout << "N" << endl;
	}
	return 0;
}

我直接好家伙。。。