U681008 #1556. [2020普转提七连测day3] 终焉之排列

CLB 有很多奇奇怪怪的想法，今天他来考你了。

CLB 有一个 $1-n$ 的排列。 但是他想知道他手里的这个排列是不是一个“终焉之排列”。 怎么定义一个排列是否是“终焉”的方法如下：\ 如果在该排列中存在两个数a, b, 且 $a + b$ 为偶数，并且 $\frac{a+b}{2}$ 在排列中的位置在 a, b 之间，则称这个排列为一个“终焉之排列”。\ 否则若不存在这样的 a, b，则不是一个“终焉之排列”。 于是 CLB 来询问你他手里的数列是否为一个“终焉之排列”。如果是输出 `YES`, 否则输出 `NO`。

该题采用**多组数据测试**： 第一行包括一个正整数 $T$ 表示数据组数； 之后包括 $T$ 组数据，每一组的格式如下：\ 第一行一个正整数 $n$，表示排列的长度。\ 第二行包括 $n$ 个互不相同的且均在 $1−n$ 范围的数用空格隔开，描述这个排列。

对于每组数据输出一行一个字符串，`YES` 或者 `NO` 。

对于 $10$ % 的数据: $1≤n≤100$ 。 对于 $40$ % 的数据: $1≤n≤1000$ 。 对于 $100$ % 的数据: $1≤n≤300000$ , $1≤T≤10$ 。 ::::success[题解] 看到这个 $\frac{x+y}2$ 非常恶心，所以我们枚举 $a_i=\frac{x+y}2$，那么问题就转化成了找到前后的 $x,y$ 使得 $x+y=2a_i$。然后我们维护前后各两个 `bitset`，具体定义如下： 1. `f1[x] = 1` 等价于 $a[1:i-1]$ 里面有 $x$ 2. `g1[2 * n - x] = 1` 等价于 $a[1:i-1]$ 里面有 $x$ 3. `f2[x] = 1` 等价于 $a[i + 1:n]$ 里面有 $x$ 4. `f1[2 * n - x] = 1` 等价于 $a[i+1:n]$ 里面有 $x$ 如果存在 $x+y=2a_i$，则 $y=2_i-x$。那么需要满足 `(f1[x] & f2[2 * a[i] - x) || (f2[x] & f1[2 * a[i] - x)`。我们一第一种情况来举例： $$ \begin{align*} f1[x]\wedge f2[2a_i-x]&\Leftrightarrow f1[x]\wedge g2[2n-2a_i+x]\\ &\Leftrightarrow f1[x]\wedge (g2 >> (2n-2a_i))[x] \end{align*} $$ 也就是说我们只需要判断 `(f1 & (g2 >> (2 * n - 2 * a[i]))).count() > 0` 即可。代码很好写 ::::