CF452F Permutation 题解

· · 题解

题意

给定 n 的一个排列，判断是否存在 i<j<k， a_j-a_i=a_k-a_j 的三元组。

其中 n \le 3 \times 10 ^ 5。

分析

我们现在称输出 yes 的序列为好序列，输出 no 的为坏序列。

考虑序列是坏的条件。

很容易想到，对任意 1 ~ n 的数 i 来说，i - k 和 i + k 是必须在 i 的同一侧的。这其实就是一个坏序列的充要条件，但直接判是 O(n ^ 2) 的，考虑发现一些更强的性质来优化。

不难发现，i ± 1 与 i ± 3 也都得在 i 的同一侧。证明如下：

假设不在同一侧，不妨设 i ± 1 在左，i ± 3 在右。

若 i - 1 在 i + 1 前，则 i - 1，i + 1，i + 3 构成三元组，则原序列是好的，矛盾。

若 i + 1 在 i - 1 前，则 i + 1，i - 1，i - 3 构成三元组，则原序列是好的，矛盾。

同理我们可以推出，i ± 1，i ± 3，i ± 5 也是在同一侧的：

假设不在同一侧，i ± 5 在右，其余在左。

若要使得原序列是坏的，则需要满足：

则推出 i - 3 在 i - 3 前，矛盾。

因此我们可以推出一个结论：i ± k (k 为奇数且 1 \le i ± k \le n) 都是在 i 的同一侧的。完整证明如下：

先使用归纳法，假设当前已经证明 i ± 1，i ± 3，...，i ± (k - 2) 在同一侧。现在证明 i ± k 也在同一侧。

再次假设不在同一侧，i ± k 在右，其余在左。

对于在左的 i ± x：

对于 i - x 与 i - k 来说，i - x 应在 2(i - x) - (i - k) 之前，否则会形成三元组。

对于 i + x 与 i + k 来说，i - x 应在 2(i - x) - (i - k) 之前，否则会形成三元组。

若把这些条件连成边，则每个左边的点都会引出一条出边，且终点也在这个范围内。即这是一个基环树，则因为有环，所以矛盾。

证毕。

类似地，我们可以推出，对于固定的 i 和 a，i ± 2 ^ a \times k (k 为奇数且 1 \le i ± 2 ^ a \times k \le n) 都在同一侧。

现在我们来证明他是推出坏序列的充分必要条件：

首先他肯定是必要的，因为这是我们推出来的条件。

其次他显然是充分的，因为经过这些条件排除后，对于每一个 i，任何 i ± k ( 1 \le i ± k \le n) 都不会出现在 i 的两侧。

所以他是充分且必要的。

这个结论有什么用呢？

我们发现，k 是一步一步往外扩展的，

所以他应该是一个前缀或后缀的形式。

而我们要判断的相当于是，对于每个 i 和 a，是否这些前缀或后缀上的数的下标是否 都大于 或 都小于 i 的下标，并且这些数都是 \bmod \ 2 ^ {a + 1} 的同余类。

所以我们枚举 a，接着处理这些前缀与后缀上的数的 下标的最大值和最小值，然后进行判定即可。时间复杂度 O(n\log n)。

Code

#include <iostream>
const int N = 1e5;
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1 ++ )
bool is_num(char ch) {return '0' <= ch && ch <= '9';}
char buf[1000000], *p1 = buf, *p2 = buf;
int read() {
    char ch;
    int f = 1;
    int x = 0;
    while (!is_num(ch = gc())) if (ch == '-') f = -1;
    do x = (x << 1) + (x << 3) + ch - '0'; while (is_num(ch = gc()));
    return f * x;
}
int pos[N + 5];
int mnpre[N + 5], mxpre[N + 5]; // 前缀下标最小与最大
int mnsuf[N + 5], mxsuf[N + 5]; // 后缀下标最小与最大
int main()
{
    int n = read();
    for (int i = 1; i <= n; i ++ ) pos[read()] = i; //每个数的下标
    for (int k = 2; k <= n; k *= 2) //枚举 2 ^ (a + 1)
    {
        for (int i = 1; i <= n; i ++ ) // 处理每个同余类的前缀的下标最小最大 
        {
            mnpre[i] = i <= k ? pos[i] : min(mnpre[i - k], pos[i]);
            mxpre[i] = i <= k ? pos[i] : max(mxpre[i - k], pos[i]);
        }
        for (int i = n; i >= 1; i -- ) // 处理每个同余类的后缀的下标最小最大
        {
            mnsuf[i] = i + k > n ? pos[i] : min(mnsuf[i + k], pos[i]);
            mxsuf[i] = i + k > n ? pos[i] : max(mxsuf[i + k], pos[i]);
        }
        for (int i = 1 + k / 2; i <= n - k / 2; i ++ ) // 枚举有贡献的 i 
        {
            int l = (i - k / 2 - 1) / k, r = (n - i - k / 2) / k; // 计算 k 往左和往右分别能扩展多少步 
            int max, min;
            if (l <= r) min = mnpre[i + k / 2 + k * l], max = mxpre[i + k / 2 + k * l]; // 如果 l <= r, 则是前缀
            else min = mnsuf[i - k / 2 - k * r], max = mxsuf[i - k / 2 - k * r]; // 否则是后缀
            if (min < pos[i] && pos[i] < max) {puts("yes"); return 0;} // 如果 i 被夹在这些数中间, 即这些数不在 i 的同一侧, 则原序列是好的 
        }
    }
    puts("no");
    return 0;
}