题目大意

给一个1到N的排列\(A_i\)，询问是否存在\(p_i\),\(i>=3\)，使得\(A_{p_1}, A_{p_2}, ... ,A_{p_len}\)是一个等差序列。

题解

显然，我们只需要找到\(P_1, P_2, P_3\)，使得其为等差数列即可。

考察等差数列的定义，不难得出：

考察每一个\(P_2\)，如果有\(P_2 - d\)已经出现，\(P_2 + d\)没有出现，那么一定可以组成等差序列。

我们考虑使用线段树维护每一个数字是否出现。如果一个数满足要求，以这个数开头的正序串和逆序串一定是不同的。我们维护每一个区间的哈希值，比较即可。

由于维护时满足区间查询，单点修改，所以我们使用线段树。

这个题WA了八次，最后找root要了数据才发现自己哈希的时候使用的pow数组用了int，结果溢出了orz

代码

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <iostream>

#define ll long long

#define mod 1000000007

#define p 3

using namespace std;

const int maxn = 10005;

struct seg {

  int l, r;

  ll hash1, hash2;

} t[maxn * 4];

int n, T;

ll pow[maxn];

void update(int k, ll m) {

  ll tmp = m >> 1;

  t[k].hash1 = ((t[k << 1].hash1 * pow[tmp]) % mod + t[k << 1 | 1].hash1) % mod;

  t[k].hash2 =

      ((t[k << 1 | 1].hash2 * pow[m - tmp]) % mod + t[k << 1].hash2) % mod;

}

void add(int k, int pos) {

  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;

  if (l == r) {

    t[k].hash1 = t[k].hash2 = 1;

    return;

  }

  if (pos <= mid)

    add(k << 1, pos);

  else

    add(k << 1 | 1, pos);

  update(k, r - l + 1);

}

ll query(int k, int x, int y, int opt) {

  if (x > y)

    return 0;

  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;

  if (x <= l && r <= y) {

    if (opt == 1)

      return t[k].hash1;

    else

      return t[k].hash2;

  }

  if (y <= mid)

    return query(k << 1, x, y, opt);

  else if (x > mid)

    return query(k << 1 | 1,x , y, opt);

  else {

    if (opt == 1) {

      return ((query(k << 1, x, mid, 1) * pow[y - mid]) % mod+

              query(k << 1 | 1, mid + 1, y, 1) % mod) %

             mod;

    } else

      return ((query(k << 1, x, mid, 2) +

              query(k << 1 | 1, mid + 1, y, 2) * pow[mid - x + 1])%mod) %

             mod;

  }

}

void build(int k, int l, int r) {

  t[k].l = l, t[k].r = r;

  if (l == r) {

    t[k].hash1 = t[k].hash2 = 0;

    return;

  }

  int mid = (l + r) >> 1;

  build(k << 1, l, mid);

  build(k << 1 | 1, mid + 1, r);

  update(k, r - l + 1);

}

int main() {

  //freopen("sequence.in", "r", stdin);

  //freopen("sequence.out", "w", stdout);

  scanf("%d", &T);

  //pow[0] = 1;

  pow[1] = p;

  for (int i = 2; i <= 10001; i++)

    pow[i] = (pow[i - 1] * p) % mod;

  while (T--) {

    scanf("%d", &n);

    build(1, 1, n);

    //memset(t, 0, sizeof(t));

    int flag = 0;

    int a[maxn];

    memset(a, 0, sizeof(a));

    for (int i = 1; i <= n; i++)

      scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++) {

      int x = a[i];

      ll len = min(x - 1, n - x);

      ll tmp1 = query(1, x - len, x - 1, 1);

      ll tmp2 = query(1, x + 1, x + len, 2);

      if (tmp1 != tmp2) {

        flag = 1;

        break;

      }

      add(1, x);

    }

    if (flag)

      printf("Y\n");

    else

      printf("N\n");

  }

}