传送们

中文题目不做翻译。题意抽象出来就是问，给定一个序列，是否存在三个顺序数字（不一定连续）能构成等差数列。

枚举中间数，构成等差数列的两个数一定是和自己距离相等的两个数字。

把数字放在数轴上，观察，其实就是求是否存在以x为中心的非回文串。

判断是否是回文可以用字符串hash在O(1)的时间里完成判断。但是这题的需要判断是否存在一个序列前缀构成的数轴是否是非回文，简单来说就是需要动态维护这个hash值。

字符串hash实际上是一种前缀和

回忆字符串hash的离线构造

f[i] = f[i – 1] * base + s[i]

可以发现明显的前缀和性质，但不同的是，在每个数累加前缀的时候是乘上了一个base。树状数组每个节点所存贮的是[x – lowbit(x) + 1, x]的和。
在修改的时候需要向上累加。这个时候只需要把对应的值乘上它的次方数就可以了。
在求和的时候是向下累加，这个时候每访问到一个节点，它代表的值仅仅是[?, i]所代表的hash值，而在[?, x]中[?, i]的hash值应该已经被乘上了对应的次方。所以在这个地方也要处理一下。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn = 1e4 + 233;
int n;
ull p[maxn];
struct BIT{
    ull c[maxn];
    void init()
    {
        memset(c, 0, sizeof c);
    }
    void add(int x)
    {
        for(int i = x; i <= n; i += i & -i) c[i] += p[i - x];
    }
    ull ask(int x)
    {
        ull res = 0;
        for(int i = x; i; i -= i & -i) res += c[i] * p[x - i];
        return res;
    }
    ull get(int l, int r)
    {
        return ask(r) - ask(l - 1) * p[r - l + 1];
    }
}h, rh;
int main()
{
    int T; cin >> T;
    p[0] = 1;
    for(int i = 1; i <= 10000; i++) p[i] = p[i - 1] * 131;
    while(T--)
    {
        int flag = 0;
        cin >> n;
        h.init(); rh.init();
        // cerr << "st" << endl;
        for(int i = 1; i <= n; i++)
        {
            int x; scanf("%d", &x);
            if(flag) continue;
            int y = n - x + 1;
            int len = min(x - 1, n - x);
            // cerr << len << endl;
            if(h.get(x - len, x + len) == rh.get(y - len, y + len)) 
            {
                // cerr << "st" << endl;
                h.add(x); rh.add(y);
            }
            else 
            {
                cout << "Y" << endl;
                flag = 1;
            }

        }
        if(!flag) cout << "N" << endl;
    }
}