How did forever fade so soon?
所谓的永远怎会如此仓促逝去
题目链接
挺有意思的题目。
显然的，只需要找出 \(len = 3\) 的等差序列是否存在就好了。
对于等差序列，我们可以发现第二个数字非常有意思，令其为 \(a_i\)，则其左边的数字为 \(a_i - k\)，右边的数字为 \(a_i + k\)。
那么，问题也就变成了对于每一个 \(a_i\) ，是否有数字 \(k\) ，满足其左边存在 \(a_i - k\)，右边存在 \(a_i + k\)。
如果直接暴力的做是 \(O(n^2)\) 的，考虑优化。
由于题目已经保证了 \(a\) 是排列，因此，从左到右遍历，如果 \(a_i - k\) 存在过并且 \(a_i+k\) 还没有出现，那么就认为找到了答案。
但是这样子正着做并不容易，因此尝试正难则反。如果没能找到答案，那么就是对于任意的 \(a_i - k\) ，满足 \(a_i+k\) 都出现了。然后问题变成了串串题。可以使用字符串哈希+线段树维护。具体可以看代码。
Code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ull unsigned long long
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N = 5e5 + 10;
const ull base = 31;
int a[N];
ull pw[N];
int n;
struct dat{int len;ull val;dat operator + (const dat oth){dat re;re.len = len + oth.len;re.val = val * pw[oth.len] + oth.val;return re;}
};
struct hash1{dat tre[N << 2];void pushup(int p){tre[p] = tre[p*2] + tre[p*2+1];return ;}void build(int pl,int pr,int p){if(pl == pr){tre[p].len = 1;tre[p].val = 0;return ;}int mid = pl + pr >> 1;build(pl,mid,p*2);build(mid+1,pr,p*2+1);pushup(p);}void update(int x,int pl,int pr,int p){if(pl == pr){tre[p].val = 1;return ;}int mid = pl + pr >> 1;if(x <= mid) update(x,pl,mid,p*2);else update(x,mid+1,pr,p*2+1);pushup(p);}dat query(int L,int R,int pl,int pr,int p){if(L <= pl && pr <= R) return tre[p];int mid = pl + pr >> 1;dat re;re.val = 0;re.len = 0;if(L <= mid) re = re + query(L,R,pl,mid,p*2);if(R > mid) re = re + query(L,R,mid+1,pr,p*2+1);return re;}
}hsh1;
struct hash2{dat tre[N << 2];void pushup(int p){tre[p] = tre[p*2+1] + tre[p*2];return ;}void build(int pl,int pr,int p){if(pl == pr){tre[p].len = 1;tre[p].val = 0;return ;}int mid = pl + pr >> 1;build(pl,mid,p*2);build(mid+1,pr,p*2+1);pushup(p);}void update(int x,int pl,int pr,int p){if(pl == pr){tre[p].val = 1;return ;}int mid = pl + pr >> 1;if(x <= mid) update(x,pl,mid,p*2);else update(x,mid+1,pr,p*2+1);pushup(p);}dat query(int L,int R,int pl,int pr,int p){if(L <= pl && pr <= R) return tre[p];int mid = pl + pr >> 1;dat re;re.val = 0;re.len = 0;if(L <= mid) re = query(L,R,pl,mid,p*2) + re;if(R > mid) re = query(L,R,mid+1,pr,p*2+1) + re;return re;}
}hsh2;
void solve(){cin >> n;hsh1.build(1,n,1);hsh2.build(1,n,1);for(int i=1;i<=n;i++)cin >> a[i];for(int i=1;i<=n;i++){hsh1.update(a[i],1,n,1);hsh2.update(a[i],1,n,1);int len = min(a[i]-1,n-a[i]);ull ans1 = hsh1.query(a[i]-len,a[i]+len,1,n,1).val;ull ans2 = hsh2.query(a[i]-len,a[i]+len,1,n,1).val;if(ans1 != ans2){cout << "Y\n";return ;}}cout << "N\n";return ;
}
int main()
{IOS;pw[0] = 1;for(int i=1;i<N;i++)pw[i] = pw[i-1] * base;int T;cin >> T;while(T -- ) solve();return 0;
}