题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(3 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你需要从$a$中恰好删除一个数，得到长为$n-1$的数组$a’$。然后生成一个长为$n-2$的数组$b$，其中$b[i]=GCD(a’[i],a’[i+1])$。

你需要让数组$b$是非降序列，即$b[i] \leq b[i+1]$。

能否做到？输出YES或NO。

输入样例

12
6
20 6 12 3 48 36
4
12 6 3 4
3
10 12 3
5
32 16 8 4 2
5
100 50 2 10 20
4
2 4 8 1
10
7 4 6 2 4 5 1 4 2 8
7
5 9 6 8 5 9 2
6
11 14 8 12 9 3
9
5 7 3 10 6 3 12 6 3
3
4 2 4
8
1 6 11 12 6 12 3 6

输出样例

YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES

算法

前后缀分解

先做个前后缀分解的预处理，预处理得到$pre$和$suf$两个数组。$pre[i]$表示$a$的前缀$[1,i]$按照题中构造方法能够构造出来的$b$的最长不递减后缀长度；$suf[i]$表示$a$的后缀$[i,n]$按照题中构造方法能够构造出来的$b$的最长不递减前缀长度。以$pre[i]$为例进行说明，令$p=gcd(a[i-2],a[i-1]),c=gcd(a[i-1],a[i])$，只要$p \leq c$成立，说明在前缀$[1,i-1]$上构造出来的$b$（以$p$结尾）在后面添加一个$c$能让$b$的非递减长度更长，$pre[i]=pre[i-1]+1$；否则$pre[i]$的值是什么就无关紧要了，因为$a[i]$被删除肯定满足不了要求。

然后枚举删除的元素$a[i]$，只要满足$gcd(a[i-2],a[i-1]) \leq gcd(a[i-1],a[i+1]) \leq gcd(a[i+1],a[i+2])$，且$pre[i-1]=i-2$，$suf[i+1]=n-i-1$。说明删除$a[i]$构造出来的$b$是单调不减的，只要存在一个这样的$i$就行。但要注意在$i=1,2,n-1,n$时以上判断条件会出现数组越界，可以特判解决，但想起来费劲，不如枚举这四种情况，检查构造出来的$b$是不是单调不减，反正也只需要$4$次$O(n)$。

复杂度分析

时间复杂度

预处理出$pre$和$suf$的时间复杂度为$O(n)$，枚举删除位置$i$计算答案的时间复杂度也是$O(n)$，所以整个算法的时间复杂度就是$O(n)$。

空间复杂度

$pre$和$suf$的空间消耗是线性的，在枚举$i=1,2,n-1,n$四种情况时需要确实地构造出$a’$和$b$两个数组，空间消耗也是线性的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int T, n, a[N], pre[N], suf[N];

void solve() {
    pre[2] = 1;
    suf[n - 1] = 1;
    for(int i = 3; i <= n; i++) {
        int p = __gcd(a[i - 2], a[i - 1]), c = __gcd(a[i - 1], a[i]);
        pre[i] = pre[i - 1] + (p <= c? 1: 0);
    }
    for(int i = n - 2; i >= 1; i--) {
        int s = __gcd(a[i + 1], a[i + 2]), c = __gcd(a[i + 1], a[i]);
        suf[i] = suf[i + 1] + (c <= s? 1: 0);
    }
    // 删除1或n
    bool ok = false;
    // 删除[3,n-2]
    for(int i = 3; i <= n - 2 && !ok; i++) {
        // 删除a[i]
        int l = __gcd(a[i - 2], a[i - 1]);
        int m = __gcd(a[i - 1], a[i + 1]);
        int r = __gcd(a[i + 1], a[i + 2]);
        if(pre[i - 1] == i - 2 && suf[i + 1] == n - i - 1 && (l <= m && m <= r)) {
            ok = true;
        }
    }
    // 删除前两个或后两个元素
    if(!ok) {
        unordered_set<int> pos{1, 2, n - 1, n};
        for(int index: pos) {
            // 删除index
            vector<int> arr;
            for(int i = 1; i <= n; i++) {
                if(i == index) continue;
                arr.push_back(a[i]);
            }
            vector<int> b;
            for(int i = 1; i < arr.size(); i++) {
                b.push_back(__gcd(arr[i - 1], arr[i]));
            }
            ok = is_sorted(b.begin(), b.end());
            if(ok) break;
        }
    }
    puts(ok? "YES": "NO");
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        solve();
    }
    return 0;
}